Morris Traversal (O(1) Space)

Morris Traversal: Tree Traversal in $O(1)$ Space

Every standard tree traversal, whether recursive DFS or iterative with an explicit stack, consumes $O(h)$ auxiliary space, where h is the height of the tree. For a balanced tree that is $O(\log n)$, and for a degenerate (linked-list-shaped) tree that is $O(n)$. Morris traversal eliminates this overhead entirely, achieving $O(1)$ extra space by temporarily borrowing unused pointer slots in the tree itself.

The Core Idea: Threading

In a binary tree, every node with a left subtree has an inorder predecessor: the rightmost node of that left subtree. After visiting the entire left subtree, the traversal needs to return to the current node. Normally a call stack handles this implicitly. Morris traversal makes it explicit: it temporarily sets the predecessor's right pointer to point back up at the current node, creating a "thread." When the traversal follows that right pointer and arrives back at the current node a second time, it knows the left subtree is done, removes the thread, visits the current node, and continues right.

The tree is fully restored by the time traversal completes, and no permanent modifications are made.

The Algorithm Step by Step

Set current = root. Then loop:

• If current has no left child, there is nothing to thread. Visit current and move to current.right. (This right pointer is either a genuine child or a thread installed earlier.)
• If current has a left child, find the inorder predecessor: start at current.left and follow .right until reaching a node whose right is either None or current itself.
• If pred.right is None: this is the first visit. Install the thread (pred.right = current) and descend left (current = current.left).
• If pred.right is current: the traversal has returned via the thread. Remove it (pred.right = None), visit current, and move right.

Walked Example

Consider this tree:

    4
   / \
  2   5
 / \
1   3

Start: current = 4. Left exists. Find predecessor of 4: follow 2 → 3, predecessor is node 3. 3.right is None, so set 3.right = 4. Move left: current = 2.

current = 2. Left exists. Find predecessor: node 1. 1.right is None, set 1.right = 2. Move left: current = 1.

current = 1. No left child. Visit 1. Move right via thread: current = 2.

current = 2. Left exists. Find predecessor: node 1. 1.right == 2, so the thread exists. Remove it (1.right = None). Visit 2. Move right: current = 3.

current = 3. No left child. Visit 3. Move right via thread: current = 4.

current = 4. Left exists. Find predecessor: follow 2 → 3, 3.right == 4, so the thread exists. Remove it. Visit 4. Move right: current = 5.

current = 5. No left child. Visit 5. Move right: None. Done.

Output: 1, 2, 3, 4, 5, the correct inorder.

The Code

def morris_inorder(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                result.append(current.val)
                current = current.right
    return result

Why It Is Still $O(n)$ Time

The inner while loop looks like it could make the algorithm quadratic, since it traverses the right spine of a left subtree each time it visits a node. But every edge in the tree is traversed at most twice: once when installing a thread (walking right to find the predecessor), and once when removing it (walking right again to confirm the thread). No edge is visited a third time. So the total work across all inner loops is $O(n)$, and the outer loop also runs $O(n)$ times, giving $O(n)$ overall despite the nested structure.

Preorder Variant

For preorder (root before left subtree), the only change is when you collect the value. In inorder you visit when you arrive via a thread (second encounter). In preorder you visit on the first encounter, right before installing the thread and descending left:

def morris_preorder(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                result.append(current.val)   # visit here, not on return
                pred.right = current
                current = current.left
            else:
                pred.right = None
                current = current.right
    return result

The structure is identical; only the placement of the append call changes.

Applications

Recover BST (LeetCode 99). In a valid BST, inorder traversal produces a strictly increasing sequence. If two nodes were accidentally swapped, the sequence will have either one or two inversions, places where prev.val > current.val. Morris traversal lets you find and fix those two nodes in $O(1)$ space. The key is tracking a prev pointer alongside current and recording the first and second violation:

def recover_tree(root):
    first = second = prev = None
    current = root
    while current:
        if not current.left:
            if prev and prev.val > current.val:
                second = current
                if not first:
                    first = prev
            prev = current
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                if prev and prev.val > current.val:
                    second = current
                    if not first:
                        first = prev
                prev = current
                current = current.right
    if first and second:
        first.val, second.val = second.val, first.val

BST to Greater Sum Tree (LeetCode 538). Visiting nodes in reverse inorder (right subtree, then root, then left subtree) while accumulating a running sum converts a BST into a Greater Sum Tree, where each node's value becomes the sum of all values greater than or equal to it. The Morris pattern applies here too: just swap left and right throughout the algorithm. This gives $O(1)$ space where a recursive solution would use $O(h)$.

Morris traversal is a niche but elegant technique. Reach for it when a problem explicitly constrains you to $O(1)$ extra space on a tree traversal, or when traversing a very deep tree where stack overflow is a genuine concern.

Recognizing this pattern

You're probably looking at Morris traversal when:

• The problem explicitly forbids recursion and an explicit stack, demanding $O(1)$ extra space on a tree walk.
• A standard inorder iterator solution would pass, but follow-up constraints rule out the $O(h)$ stack.
• The tree is extremely deep and you cannot afford the recursion stack, while the input is mutable (or you can restore the mutations).
• You need an inorder, preorder, or reverse-inorder visit order and threading via temporarily reused right-child pointers is acceptable.

Common templates:

• Morris inorder: thread the rightmost node of the left subtree back to the current node, then unthread on the second visit. Example: Binary Tree Inorder Traversal.
• Recover BST with two swapped nodes: Morris inorder while tracking out-of-order pairs. Example: Recover Binary Search Tree.
• Reverse Morris (right-root-left): swap left and right in the threading to accumulate from largest to smallest. Example: Binary Search Tree to Greater Sum Tree.
• Morris preorder: emit the current node when first establishing the thread instead of when removing it. Example: Binary Tree Preorder Traversal.