Leaving a trail in the pointers you weren't using
Recursive traversal borrows the call stack's memory. A threaded tree avoids that entirely by repurposing NULL pointers into a trail straight to the next node.
After this lesson
You should be able to
- Explain what memory cost ordinary traversal has that threading avoids.
- Explain what a NULL right pointer means in a right-threaded tree.
- Describe how a boolean flag distinguishes a thread from a real child pointer.
The cost recursion hides
Every recursive call in Lesson 3's traversal functions sits on the call stack until it returns — for a tree of height h, that is up to h pending calls at once, exactly like Unit I's recursion lessons in CS105ES. An iterative traversal without recursion needs an explicit stack instead, which is the same memory cost wearing a different name.
A threaded binary tree asks a sharper question: a leaf's right pointer is NULL anyway, doing nothing. What if that unused pointer pointed somewhere useful instead?
A thread is a trail to what comes next
In a right-threaded tree, if a node has no right child, its right pointer is repurposed to point directly at its inorder successor — the node that Lesson 6 already taught you how to find, the leftmost node of the right subtree, generalized to 'wherever inorder visits next.' Left threading does the same thing backward, pointing NULL left pointers at the inorder predecessor.
Think of it as leaving a breadcrumb trail — like Hansel and Gretel, so that once you reach a dead end, a thread already laid down tells you exactly where to go next, with no need to backtrack through everywhere you have already been.
struct Node {
int data;
struct Node *left;
struct Node *right;
int rightIsThread; /* 1 = right points to inorder successor, not a child */
};What this buys you
With threads in place, finding the inorder successor of any node is a direct pointer follow when rightIsThread is set — no stack, no recursion, no climbing back up through parents. A full inorder traversal becomes a simple loop: keep following the thread or the leftmost path, with no extra memory beyond a couple of pointers.
The trade is real, not free: every insertion and deletion must now also maintain the threads correctly, which is extra bookkeeping on every write in exchange for cheaper traversal reads.
Try it yourself
For the tree with root 30, left child 20, right child 40 (all leaves except the root), identify every thread: which NULL pointers become threads, and what does each point to?
Need a hint?
Write out the inorder sequence first — 20, 30, 40 — then each thread points at whatever comes next in that sequence.
Check the worked solution
20's right pointer threads to 30 (its inorder successor). 40's right pointer would thread to nothing — it is the last node inorder, so it stays NULL to mark the true end. 20's left pointer and 40's left pointer both thread to nothing meaningful before them beyond the root, so implementations typically leave the very first and last positions as plain NULL, or point them at a sentinel node — a detail worth checking against whatever textbook convention a course follows.
Quick check
In a right-threaded binary tree, what does it mean when a node's rightIsThread flag is set?
Why this lesson exists
Syllabus mapping
Threaded Binary Trees
Maps to course outcomes CO1, CO4.