Morris Traversal: Inorder Tree Traversal in O(1) Extra Space

Recursive and stack-based inorder traversals use O(h) extra space, where h is the tree height. A follow-up interviewers like is: "Can you do it in O(1) space?" Morris traversal is the answer.

The trick: temporary threads

Before descending into a node's left subtree, find that node's inorder predecessor (the rightmost node of the left subtree) and point its empty right pointer back at the current node. When the traversal later reaches the predecessor, that thread leads back up, replacing the stack. On the second visit, remove the thread to restore the tree.

def morris_inorder(root):
    out, cur = [], root
    while cur:
        if cur.left is None:
            out.append(cur.val)
            cur = cur.right
        else:
            pre = cur.left
            while pre.right and pre.right is not cur:
                pre = pre.right
            if pre.right is None:        # first visit: create thread
                pre.right = cur
                cur = cur.left
            else:                        # second visit: remove thread
                pre.right = None
                out.append(cur.val)
                cur = cur.right
    return out

Why it's still O(n) time

The inner loop that searches for predecessors looks expensive, but each edge of the tree is walked at most a constant number of times (once to create the thread and once to remove it), so total work is O(n).

Variants

• Preorder: output the node when you create the thread instead of when you remove it.
• Postorder: possible, but requires reversing right-edge paths when removing threads; mention that it exists rather than coding it under time pressure.

Problems where it shines

• Recover a BST where two nodes were swapped, in O(1) space.
• Kth smallest element in a BST without extra memory.
• Validate a BST iteratively with constant space.

Caveats to state

The tree is temporarily modified, so it isn't safe with concurrent readers, and an early return mid-traversal can leave threads in place. If you stop early, finish removing threads or explain the trade-off.

Disclosure: I work on Linkjob AI, which helps with live coding interviews. These notes are general study material.