Threaded Tree Traversal

March 2026 · 14 min read

The Problem: Why Is Standard Traversal Expensive?

In a normal binary tree, in-order traversal requires auxiliary space, either the implicit call stack of recursion or an explicit stack data structure. Both cost O(h) space, where h is the tree height.

Why? Because after visiting the entire left subtree of a node, we need to find our way back to the node itself. In a standard tree, there are no upward links, the only way back is to have saved the node on a stack before going left.

The Core Idea

In a right-threaded BST, every node whose right child would normally be null instead has a thread pointing to its in-order successor. This means:

• After visiting a node with no right subtree, we don't need a stack to find what comes next, we just follow the thread.
• After visiting a node with a right subtree, we go to the leftmost node of that subtree (the smallest element there).

These two rules completely eliminate the need for a stack. The threads serve as built-in "return addresses."

The Algorithm, Step by Step

Starting Point

We start at the leftmost node in the entire tree. This is the smallest element, the first node in the in-order sequence. To find it, we simply keep going left from the root until we can't anymore:

ThreadedNode* leftmost(ThreadedNode* node) {
    while (node && node->left && !node->leftThread)
        node = node->left;
    return node;
}

But Wait: Why Don't We Visit Nodes on the Way Down?

This is the most common source of confusion. Consider this tree with root 4:

        4
       / \
      2   6
     / \
    1   3

We go from 4 → 2 → 1 and only visit node 1. Why did we "skip" nodes 4 and 2?

The answer comes directly from what in-order means: for every node, you must finish its entire left subtree before you visit the node itself. That's the definition, Left, Root, Right.

Let's trace the logic concretely:

• Can we visit 4 first? No. In-order says: visit 4's entire left subtree first. That left subtree contains {1, 2, 3}. So 4 must wait until after 1, 2, and 3 are all done.
• Okay, can we visit 2 first? Still no. In-order says: visit 2's entire left subtree first. That left subtree contains {1}. So 2 must wait until after 1 is done.
• Can we visit 1 first? Yes! Node 1 has no left subtree (or its left is a thread, not a child). There's nothing that must come before 1. So 1 is the correct first node to visit.

So how do 4 and 2 eventually get visited? They don't get forgotten, the threads bring us back to them! After visiting 1, node 1's right-thread points to 2 (its in-order successor). After visiting 2 and its right subtree (3), node 3's right-thread points to 4. The threads act as "reminders" that guide us back to each skipped node at exactly the right moment.

This is also why the same leftmost() logic appears in Case 2 below. When we visit a node and it has a right subtree, the next in-order node is the leftmost of that right subtree, for the same reason: we must finish the left side of that subtree before visiting anything else in it.

The Main Loop

Once we're at the leftmost node, we repeatedly ask: "What comes next?" There are exactly two cases:

Case 1: The node is right-threaded (rightThread == true)

The right pointer is a thread to the in-order successor. We simply follow it:

cur = cur->right;  // follow thread — O(1), no searching needed

Why this works: During construction, we specifically set this pointer to point to the node that comes next in in-order sequence. The thread is essentially a pre-computed "next" link.

Case 2: The node has a real right child (rightThread == false)

There's a right subtree. The next node in in-order is the leftmost (smallest) node in that subtree:

cur = leftmost(cur->right);  // go right once, then all the way left

Why this works: In-order traversal visits left subtree, then root, then right subtree. When we finish processing a node and it has a right subtree, the next thing to visit is the leftmost element of that right subtree.

Termination

The loop ends when cur becomes null. This happens when the last node in the in-order sequence (the rightmost node in the tree) has rightThread == true and its right pointer is null (no successor exists).

Detailed Walkthrough

Let's trace the algorithm on this right-threaded BST with nodes [1, 2, 3, 4, 5, 6, 7]. Threads (dashed) go from 1→2, 3→4, and 5→6:

Observation: At every step, we either follow a thread (O(1)) or descend to the leftmost of a right subtree. Over the entire traversal, each edge in the tree is followed at most twice. Total work: O(n).

Complete C++ Implementation

Here's the full implementation with detailed comments explaining each decision:

// Helper: find the leftmost node in a subtree
// This is always the first node to visit in an in-order traversal
ThreadedNode* leftmost(ThreadedNode* node) {
    if (!node) return nullptr;
    while (node->left && !node->leftThread)
        node = node->left;     // keep going left while it's a real child
    return node;               // either a leaf or a doubly-threaded node
}

// In-order traversal: O(n) time, O(1) space
void threadedInorder(ThreadedNode* root) {
    ThreadedNode* cur = leftmost(root);   // start at smallest node

    while (cur) {
        visit(cur);                        // process current node

        if (cur->rightThread) {
            cur = cur->right;              // Case 1: follow thread to successor
        } else {
            cur = leftmost(cur->right);    // Case 2: leftmost in right subtree
        }
    }
    // When cur becomes null, we've visited all nodes
}

Why leftmost() Is Correct

The leftmost function stops when it encounters a null left pointer or a left thread. In a doubly-threaded tree, left threads point to predecessors, not children, following them would go backward. The check !node->leftThread ensures we only follow real child pointers.

In a singly (right-only) threaded tree, leftThread is always false, so the check simplifies to just while (node->left).

Why This Produces In-order Sequence

Let's prove this more rigorously. In-order traversal visits: left subtree, root, right subtree. Our algorithm maintains this invariant:

1. We start at the leftmost node. This is correct, it's the node with no left subtree (or whose entire left subtree has been "skipped" because we started at the bottom).
2. After visiting a node, the next in-order node is either:
   • The leftmost node in its right subtree (if one exists), this is the start of the right subtree's in-order.
   • Its in-order successor further up the tree (if no right subtree), the thread provides this directly.

In both cases, we jump to exactly the right node. No node is skipped, and no node is visited twice. The output is exactly the in-order sequence.

Connection to Morris Traversal

Morris traversal (covered in detail in the next post) achieves the exact same O(1)-space in-order traversal on a standard (unthreaded) tree. It does this by creating temporary threads on the fly, using them to traverse, and then removing them.

The relationship is straightforward:

When to use which:

• If the tree is traversed many times → threaded tree (amortize construction cost)
• If you can't store extra bits per node → Morris (no permanent modification)
• If the tree is read-only → neither works; use a stack
• If concurrent reads are needed → threaded tree (Morris has data races)

Pre-order Traversal on Threaded Trees

Pre-order (root, left, right) is also possible without a stack. The idea: visit the node immediately, then go left if possible. When there's no left child, go right. When there's no right child either, follow threads upward until we find a node with an unvisited right subtree.

The Algorithm

1. Visit the current node (pre-order visits before children).
2. If it has a real left child → go left.
3. If it has a real right child (but no left) → go right.
4. If it's a leaf (both threaded or null) → follow right threads upward until we find a node with a real right child. Go to that right child.

void threadedPreorder(ThreadedNode* root) {
    ThreadedNode* cur = root;
    while (cur) {
        visit(cur);                         // visit FIRST (pre-order)

        if (!cur->leftThread && cur->left) {
            cur = cur->left;                // go to left child
        } else if (!cur->rightThread && cur->right) {
            cur = cur->right;               // no left, go to right child
        } else {
            // Leaf node: follow right threads upward
            // until we find a node with a real right child
            while (cur && cur->rightThread)
                cur = cur->right;           // follow thread up
            if (cur)
                cur = cur->right;           // go to the right child
        }
    }
}

Why the Thread-following Loop Works

When we're at a leaf and follow the right thread, we jump to an ancestor. That ancestor was already visited (pre-order visits before descending). We need its right subtree. If the ancestor is also threaded (no right subtree), we keep following threads until we find one with a real right child. This effectively "unwinds" the left-side descent without a stack.

Post-order Traversal on Threaded Trees

Post-order (left, right, root) is the hardest of the three standard traversals to implement on threaded trees. The reason is fundamental: post-order visits a node after both its children. This means we arrive at a node, can't visit it yet, must process both subtrees, and only then come back to visit it.

Why Threads Alone Aren't Enough

Consider the root node 4 in our tree. Post-order says: process the entire left subtree [1, 3, 2], then the entire right subtree [5, 7, 6], and only then visit 4.

After visiting 3, the right thread takes us to 4, but we can't visit 4 yet. We still need to process {5, 6, 7}. There is no thread from 3 to 5 that would let us skip over 4. The right thread goes to 4 (the in-order successor), not to 5 (the next post-order node).

The core issue: In in-order, following a thread means "visit this ancestor now", the left subtree is done and the thread delivers us to exactly the right moment. In post-order, following a thread means "I'm back at this ancestor, but I still have right-subtree work to do." Threads provide one return path per node, but post-order effectively needs two returns per internal node (once after left, once after right).

The Approach: Stack + Last-Visited Tracking

The cleanest practical approach uses a small stack (O(h) space) and tracks which node was visited last. The lastVisited pointer lets us distinguish "returned from left child" vs "returned from right child", the exact information threads can't provide:

void threadedPostorder(ThreadedNode* root) {
    if (!root) return;

    std::stack<ThreadedNode*> stk;
    ThreadedNode* cur = root;
    ThreadedNode* lastVisited = nullptr;

    while (cur || !stk.empty()) {
        // Go as far left as possible (real children only)
        while (cur) {
            stk.push(cur);
            cur = (!cur->leftThread && cur->left) ? cur->left : nullptr;
        }

        ThreadedNode* top = stk.top();

        // If top has a real right child we haven't visited yet
        if (top->right && !top->rightThread && top->right != lastVisited) {
            cur = top->right;   // explore right subtree next
        } else {
            // Both subtrees done, visit this node
            visit(top);
            lastVisited = top;
            stk.pop();
        }
    }
}

How It Works

1. Push leftward: From the current node, push every node on the leftward path onto the stack until there are no more real left children (checking !leftThread).
2. Check the top: The top of the stack is the deepest unvisited node. If it has a real right child (!rightThread) that we haven't visited yet (!= lastVisited), go right and repeat step 1.
3. Visit: If both subtrees are done (right child is a thread, null, or already visited), visit the node and pop it. Set lastVisited so the parent knows we've finished this side.

Why !rightThread Is Critical

In a standard (unthreaded) tree, we'd check top->right != nullptr to see if a right child exists. In a threaded tree, top->right might be non-null but point to the in-order successor, not a child. The !top->rightThread check ensures we only descend into real right children, not threads.

Space: O(h) Is Hard to Avoid

True O(1)-space post-order requires the reverse right-boundary technique (as in Morris post-order), which temporarily reverses chains of right-child pointers, visits them in reverse, and restores them. For an already-threaded tree, this is particularly complex because the threads (which also use right pointers) must be carefully preserved and restored. In practice, the stack-based approach is almost always preferred, O(h) is typically O(log n) for balanced trees.

The key insight: in-order and pre-order naturally follow the "forward" direction of threads. Post-order fights against this direction, which is why it requires extra machinery that threads alone can't provide.

Complexity Analysis

Time: O(n)

At first glance, Case 2 (finding the leftmost node in a right subtree) seems like it could be O(h) per step, making the total O(n·h). But this isn't the case. Here's why:

Each edge in the tree is traversed at most twice during the entire traversal, once going down (via leftmost) and once going up (via a thread). Since there are n−1 edges, the total work across all leftmost calls is O(n). Each visit is O(1). So the total is O(n).

This is the same amortized argument used for Morris traversal.

Space: O(1)

We use only a single pointer variable (cur). No stack, no recursion, no hash set. This is the entire point of threading.

Comparison Table

Threaded tree traversal is the only method that achieves O(1) space and doesn't modify the tree during traversal. The trade-off is the upfront cost of threading the tree and the boolean flags per node.

Edge Cases to Watch For

• Empty tree: leftmost(null) returns null, the loop body never executes. Correct.
• Single node: leftmost(root) returns root. We visit it. rightThread is true, right is null → loop ends. Correct.
• Left-skewed tree: leftmost descends all the way down. Then every step follows a thread back up. Each node is visited exactly once.
• Right-skewed tree: leftmost(root) returns root immediately. Then every step goes to leftmost(right), which is just the next node (no left children). Degenerates to a linked list traversal.

Real-World Applications

• Database indexes (B+ trees): Leaf pages in B+ trees are linked sequentially for efficient range scans. This is essentially threading applied to disk-based trees, once you reach the first matching leaf, you follow "next page" pointers without climbing back up the tree.
• Compiler symbol tables: Languages with ordered symbol tables (C++ std::map) use balanced BSTs internally. Threaded variants enable efficient in-order iteration over identifiers.
• Real-time systems: Stack usage is bounded and deterministic. In safety-critical systems (automotive, aerospace), guaranteed O(1) space with no recursion is a hard requirement.
• Memory-constrained devices: Embedded systems with kilobytes of RAM. A recursive traversal of a deep tree might overflow the tiny stack. Threaded traversal cannot.
• Iterator implementation: Threaded trees make it trivial to implement forward and backward iterators with O(1) next() and prev() operations.

Summary

• Threaded traversal has exactly two cases: follow a thread (O(1)) or find leftmost in right subtree.
• Start at the leftmost node. At each step, the rightThread flag tells you which case applies.
• Total time is O(n), each edge traversed at most twice, amortized over n visits.
• Total space is O(1), just one pointer variable. No stack, no recursion.
• This is the only O(1)-space traversal that doesn't modify the tree during execution.
• Pre-order traversal is also stack-free: visit first, go left, or follow threads up to find the next right subtree.
• Post-order traversal is fundamentally harder, it requires visiting both children before the parent, which threads alone can't support. A stack + lastVisited tracker is the cleanest approach (O(h) space).
• Morris traversal is the "on-the-fly threading" variant for standard (unthreaded) trees.