Morris Threaded Traversal

Description

Morris traversal walks a binary tree in order using O(1) extra space: no recursion, no stack. Before going down a node's left subtree, it makes that subtree's rightmost node point back to the node. That temporary link is called a "thread", and it lets the walk find its way back. When the walk returns along the thread, it removes it. It's the answer when the interviewer says "now without the stack".

We'll go from simple to more technical:

1. The pattern: thread, descend, come back, unthread.
2. Inorder versus preorder: the same loop, a different moment to visit.
3. Where borrowing an unused pointer saves real memory.
4. The risks: threads left behind, and mutating a tree others can see.

The approach (inorder; preorder is a one-line change)

Recursion remembers "come back here after the left subtree" on the call stack: O(h) extra space, where h is the tree's height. Morris stores that reminder inside the tree instead. In inorder, the last node visited in a node's left subtree is that subtree's rightmost node, the node's predecessor. The predecessor has no right child, so its right pointer is free. Point it at the current node, go left, and when the walk later arrives through that pointer, you know the left side is done.

TreeNode curr = root;
while (curr != null) {
    if (curr.left == null) {
        visit(curr);              // no left subtree - visit now, move right
        curr = curr.right;
    } else {
        TreeNode pred = curr.left;
        while (pred.right != null && pred.right != curr) pred = pred.right;  // find predecessor
        if (pred.right == null) {
            pred.right = curr;     // create the thread
            curr = curr.left;      // descend, without visiting curr yet (inorder: node comes after left)
        } else {
            pred.right = null;     // thread already exists - we've returned via it; remove it
            visit(curr);            // now visit curr (its left subtree is done)
            curr = curr.right;
        }
    }
}

curr = root
while curr is not None:
    if curr.left is None:
        visit(curr)              # no left subtree - visit now, move right
        curr = curr.right
    else:
        pred = curr.left
        while pred.right is not None and pred.right is not curr:
            pred = pred.right    # find predecessor
        if pred.right is None:
            pred.right = curr    # create the thread
            curr = curr.left     # descend, without visiting curr yet (inorder: node comes after left)
        else:
            pred.right = None    # thread already exists - we've returned via it; remove it
            visit(curr)          # now visit curr (its left subtree is done)
            curr = curr.right

For preorder, visit curr when you create the thread, before going left, instead of when you remove it. Nothing else changes.

Where you'll see it

O(1) space matters on small embedded devices. It also matters when many separate trees are walked at once, so stack space adds up. When "no stack, no recursion" is a hard rule rather than a preference, Morris is the standard answer.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. An implementation creates threads but never removes them. What state is the tree in afterwards?

2. What single change turns Morris inorder into Morris preorder?

3. Why does the predecessor search also stop at pred.right == curr, not just at null?

Key takeaways

• Morris borrows the predecessor's unused right pointer as a "come back here" link, so no stack is needed.
• Remove every thread on the way back, or the tree stays broken.
• Inorder visits when removing the thread; preorder visits when creating it.
• The predecessor search stops at null or at curr.
• O(1) space costs a temporarily changed tree and trickier code. Use it when the space limit is real.