Morris Traversal

March 2026 · 18 min read

In the previous post, we saw how a permanently threaded tree achieves O(1)-space in-order traversal. The threads, pointers from nodes with no right child to their in-order successor, eliminate the need for a stack entirely. But permanently threading a tree requires modifying every node (adding boolean flags), building the threads upfront, and maintaining them across insertions and deletions.

Morris traversal asks a radical question: what if we could get O(1)-space traversal on a completely standard, unmodified binary tree, no extra boolean flags, no upfront construction, no permanent changes?

The answer is yes. Morris traversal creates threads on the fly, uses them to navigate the tree, and then removes them, leaving the tree in its original state. It achieves O(n) time and O(1) space without ever building a "threaded tree" in the formal sense.

The Fundamental Insight

Why Does Recursion Need a Stack?

Say we're doing in-order traversal and we arrive at some node X that has a left subtree. We go left, and keep going deeper into that subtree until we've visited every node in it. The very last node we visit in that left subtree is the rightmost node, let's call it P.

Wait, What is an In-Order Predecessor?

The in-order predecessor of a node is simply the node that comes right before it in an in-order traversal. In-order means: left subtree, then the node itself, then right subtree. So the predecessor of X is the last node visited before X.

If X has a left subtree, that predecessor lives inside it. Specifically, it's the rightmost node in the left subtree. Why? Because in-order traversal visits the left subtree in L-N-R order, and the very last thing it touches before leaving a subtree is the rightmost node (it keeps going right until it can't anymore).

Here's a concrete example:

To find the predecessor: start at X's left child, then keep going right until you can't. That final node is P. It's the last node in-order visits before returning to X, which is exactly why it's the perfect place to plant a thread back to X.

Now we're done with the left subtree. We need to come back up to X so we can visit it and then explore its right subtree. But here's the problem: P has no pointer leading back to X. In a regular binary tree, child nodes don't know about their ancestors.

So how does recursion handle this? Before going left from X, it saves X on the call stack. When the left subtree is fully done, it pops X off the stack and picks up where it left off. That stack grows as tall as the tree, costing O(h) extra space.

The Threading Trick

Now recall what we learned about threaded trees: in a right-threaded BST, P's right pointer doesn't go to a child, it threads directly to X. That thread eliminates the need for a stack at that step.

Morris's insight: we don't need the tree to be permanently threaded. We can create this one specific thread, from the predecessor P to the current node X, right before we need it. Once we've used the thread to return to X, we remove it. The tree is temporarily modified, but it's restored to its original shape.

Why This Needs No Extra Storage

In a threaded binary tree, we need boolean flags (leftThread, rightThread) to distinguish threads from real child pointers. Morris traversal doesn't need these flags because it uses a different mechanism to tell threads apart from children: it checks whether the predecessor's right pointer points back to the current node.

When we're at node X and find the predecessor P:

• If P->right == nullptr → we haven't been here before. This is a real null pointer. Create a thread.
• If P->right == X → we created this thread earlier and have now returned via the left subtree. Remove the thread.

The predecessor's right pointer itself carries the information that boolean flags would carry in a permanent threaded tree. No extra storage needed.

The Algorithm, Step by Step

We maintain a single pointer cur, starting at the root. At each iteration:

Case 1: cur has no left child

There's no left subtree to explore. We visit cur (it's the next node in in-order) and move right: cur = cur->right.

If cur->right is a thread we created earlier, this takes us back up to the ancestor that created the thread. If it's a real child pointer, it takes us into the right subtree. Either way, we end up at the correct next node.

Case 2: cur has a left child

We need to traverse the left subtree before visiting cur. But first, we need a way to get back to cur after the left subtree is done. So we find the in-order predecessor of cur, the rightmost node in the left subtree.

Finding the predecessor

TreeNode* pred = cur->left;
while (pred->right && pred->right != cur)
    pred = pred->right;

We go one step left, then keep going right until we hit either null (the rightmost node) or cur itself (a thread we created earlier). The condition pred->right != cur is critical, it prevents us from looping forever on a thread we already set.

Sub-case 2a: pred->right == nullptr (first visit)

We've never been here before. The predecessor's right pointer is genuinely null. This is our moment to plant the thread:

pred->right = cur;   // create temporary thread
cur = cur->left;     // descend into left subtree

The thread is our breadcrumb. When the left subtree traversal eventually reaches pred and tries to go right, it will follow this thread back to cur.

We do NOT visit cur yet. In in-order traversal, we visit the left subtree first. We'll come back to cur later via the thread.

Sub-case 2b: pred->right == cur (second visit)

The predecessor's right pointer already points to cur. This means we created this thread earlier, descended into the left subtree, traversed it completely, and have now returned to cur via the thread. The left subtree is done.

pred->right = nullptr;  // remove the thread (restore original tree)
visit(cur);             // NOW visit cur (left subtree is complete)
cur = cur->right;       // move to right subtree

We remove the thread to restore the tree, visit the node (in-order: left subtree done, now the root), and proceed to the right subtree.

The Complete Code

void morrisInorder(TreeNode* root) {
    TreeNode* cur = root;

    while (cur) {
        if (!cur->left) {
            // ---- CASE 1 ----
            // No left subtree. This node is next in in-order.
            visit(cur);
            cur = cur->right;  // go right (may follow a thread)
        } else {
            // ---- CASE 2 ----
            // Has left subtree. Find in-order predecessor.
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur)
                pred = pred->right;

            if (!pred->right) {
                // ---- Sub-case 2a: First visit ----
                // Create thread and descend left.
                pred->right = cur;
                cur = cur->left;
            } else {
                // ---- Sub-case 2b: Second visit ----
                // Left subtree done. Remove thread, visit, go right.
                pred->right = nullptr;
                visit(cur);
                cur = cur->right;
            }
        }
    }
}

That's the entire algorithm. No stack. No recursion. No boolean flags. No auxiliary data structure. Just a while loop with one pointer variable.

Morris vs. Threaded Tree vs. Stack: Full Comparison

Morris Preorder Variant

The in-order version visits nodes on the second encounter (after the left subtree is done). For preorder, we want to visit on the first encounter (before descending left). The change is minimal:

void morrisPreorder(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            visit(cur);             // no left subtree: visit and go right
            cur = cur->right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur)
                pred = pred->right;

            if (!pred->right) {
                visit(cur);         // VISIT on first encounter (preorder)
                pred->right = cur;  // create thread
                cur = cur->left;    // descend left
            } else {
                pred->right = nullptr;  // remove thread
                // DON'T visit (already visited on first encounter)
                cur = cur->right;
            }
        }
    }
}

The only difference: visit(cur) moves from sub-case 2b to sub-case 2a. Everything else, thread creation, removal, cursor movement, stays identical.

Morris Postorder Variant

Post-order is where Morris traversal gets genuinely interesting. The trick itself is elegant: introduce a dummy node, and on every second encounter, reverse-visit the right boundary of the left subtree before moving on. The idea fits in a paragraph, but understanding why it works, how the pointer reversal preserves O(1) space, what the dummy node actually solves, and how each step maps to the final output requires careful, visual explanation.

It deserves its own dedicated treatment rather than being compressed into a subsection here.

When to Use Morris Traversal

Use Morris when:

• Interview optimization: Present the stack-based solution first, then mention Morris as an O(1) space optimization. Interviewers love hearing "we can actually do this in constant space by temporarily threading the tree."
• Memory-constrained environments: Embedded systems or situations where even O(h) stack space is too much.
• One-shot traversal: You only need to traverse the tree once and can tolerate temporary mutation.
• When you can't modify the node struct: Unlike permanent threading (which needs boolean flags), Morris works on standard TreeNode with just val, left, right.

Don't use Morris when:

• The tree is read-only or const, Morris needs to mutate pointers.
• Multi-threaded access without locking, the temporary cycles create data races.
• You need to traverse many times, a permanent threaded tree amortizes the threading cost.
• Exception safety matters, interruption leaves the tree corrupted.

Interactive Animations

Summary

• Morris traversal achieves O(n) time, O(1) space traversal on a standard binary tree, no permanent threading required.
• It works by creating temporary threads on the fly: pointer from the rightmost node of each left subtree back to the current node.
• Every node with a left child is visited twice: first to create the thread and descend left, second to remove the thread and go right.
• In-order: visit on the second encounter (after left subtree done). Pre-order: visit on the first encounter (before descending left). Post-order: on second encounter, reverse-visit the right boundary of the left subtree using a dummy node.
• The predecessor check (pred->right == null vs pred->right == cur) replaces the boolean flags that a permanent threaded tree would need.
• O(n) time is guaranteed by amortized analysis: each edge is used at most twice across all predecessor searches.
• The trade-off: temporary tree mutation. Not safe for concurrent access, const trees, or exception-prone code.
• For repeated traversals, permanent threading wins. For one-shot O(1)-space needs on a standard tree, Morris is unbeatable.