Morris Traversal — Stop Stack Overflow in Skewed Trees

Every serious DSA practitioner hits a wall when they realise that recursive tree traversal — elegant as it is — carries a hidden O(h) space cost on the call stack, where h is the tree height. On a skewed tree with a million nodes, that's a million stack frames. In memory-constrained environments — embedded systems, high-throughput stream processors, certain competitive programming judges — that cost is unacceptable. Morris Traversal, published by Joseph Morris in 1979, solves this with an audacious idea: temporarily rewrite the tree's own null pointers to encode traversal state, then undo every change before you leave.

The problem Morris Traversal solves is surprisingly fundamental: how do you know where to 'go back' after finishing a left subtree, without a stack keeping that address for you? The classic iterative approach just swaps the implicit call stack for an explicit one — same asymptotic cost, different constant. Morris's insight was that null right-child pointers in inorder predecessors are wasted space. There are exactly n-1 edges in a binary tree, leaving n+1 null pointers sitting idle. He used a subset of those to store temporary back-links — called 'threads' — that guide traversal back up the tree without any auxiliary structure.

By the end of this article you'll be able to implement Morris Inorder and Morris Preorder from scratch, explain the thread-creation and thread-detection logic in an interview, reason about exactly when the tree is in a temporarily modified state (and why that matters for concurrent code), and confidently handle every edge case — single nodes, skewed trees, complete binary trees, and trees with duplicate values.

What is Morris Traversal? — Plain English

Morris Traversal performs in-order traversal of a binary tree using O(1) extra space — no recursion stack, no auxiliary stack. The trick is to temporarily modify the tree by creating 'threads': right pointers that point back to the in-order successor. Normal in-order traversal uses a call stack (O(h) space) to remember where to return after finishing the left subtree. Morris Traversal avoids this by using the rightmost node of each left subtree as a bookmark — it threads a right pointer from that node back to the current node, allowing the traversal to return without a stack. After using the thread, it is removed to restore the original tree. The tree ends up unchanged after the traversal completes.

How Morris Traversal Works — Step by Step

Algorithm for in-order Morris Traversal:

1. Set current = root.
2. While current is not None:
3. a. If current has no left child: visit current (append to result), then current = current.right.
4. b. If current has a left child:
5. i. Find the in-order predecessor: the rightmost node of current.left subtree (predecessor = current.left, then go right until right is None OR right == current).
6. ii. If predecessor.right == None (no thread yet): create thread: predecessor.right = current. Move current = current.left.
7. iii. If predecessor.right == current (thread exists, we're returning): remove thread: predecessor.right = None. Visit current. Move current = current.right.
8. When current becomes None, traversal is complete.

Worked Example — Tracing Morris Traversal on a Tree

Tree: 4 / \ 2 5 / \ 1 3

In-order should produce: [1,2,3,4,5].

current=4. Has left. Predecessor of 4 = rightmost of 2's subtree = node 3 (3.right=None). Create thread: 3.right=4. Move current=2. current=2. Has left. Predecessor of 2 = rightmost of 1's subtree = node 1 (1.right=None). Create thread: 1.right=2. Move current=1. current=1. No left. Visit 1 → result=[1]. current=1.right=2 (thread). current=2. Has left. Predecessor of 2 = node 1. 1.right=2 (thread exists). Remove thread: 1.right=None. Visit 2 → result=[1,2]. current=2.right=3. current=3. No left. Visit 3 → result=[1,2,3]. current=3.right=4 (thread). current=4. Has left. Predecessor of 4 = node 3. 3.right=4 (thread exists). Remove thread: 3.right=None. Visit 4 → result=[1,2,3,4]. current=4.right=5. current=5. No left. Visit 5 → result=[1,2,3,4,5]. current=5.right=None. Done.

Implementation

Morris Traversal modifies right pointers temporarily as threads, then restores them. Finding each predecessor takes O(1) amortized time because each edge is traversed at most twice (once to create the thread, once to remove it), giving O(n) total. Space is O(1) — only a few pointers are needed. The tradeoff versus recursive DFS is increased code complexity and the temporary mutation of the tree during traversal.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val; self.left = left; self.right = right

def morris_inorder(root):
    result = []
    current = root
    while current:
        if current.left is None:
            # No left subtree: visit and move right
            result.append(current.val)
            current = current.right
        else:
            # Find in-order predecessor (rightmost of left subtree)
            pred = current.left
            while pred.right and pred.right is not current:
                pred = pred.right

            if pred.right is None:
                # Create thread back to current
                pred.right = current
                current = current.left
            else:
                # Thread exists: we've returned; remove thread
                pred.right = None
                result.append(current.val)
                current = current.right
    return result

# Build tree: 4 -> 2->1,3 and 4->5
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(1), TreeNode(3))
root.right = TreeNode(5)

print(morris_inorder(root))  # [1, 2, 3, 4, 5]

Complexity Analysis & Trade-offs

Morris Traversal runs in O(n) time and O(1) extra space. The constant factor is higher than recursive or iterative stack approaches because each node's predecessor search may traverse several edges. However, amortised analysis shows each edge is traversed at most twice: once when creating the thread and once when removing it. The total number of pointer assignments is 2*(n-1) = O(n).

Morris Preorder Traversal

The same threading idea works for preorder traversal with a slight modification: visit the node before creating the thread (or before descending into the left subtree). In inorder, you visit after removing the thread. In preorder, you visit the current node as soon as you encounter it, then create the thread and descend.

Algorithm: 1. current = root. 2. While current != None: a. If current.left is None: visit(current) current = current.right b. Else: pred = current.left while pred.right and pred.right is not current: pred = pred.right if pred.right is None: visit(current) // visit before creating thread pred.right = current current = current.left else: pred.right = None current = current.right

The key difference: in preorder, you visit the node when you first reach it (before any thread creation). In inorder, you visit after removing the thread (when returning from left subtree).

def morris_preorder(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right is not current:
                pred = pred.right
            if pred.right is None:
                result.append(current.val)  # visit before thread
                pred.right = current
                current = current.left
            else:
                pred.right = None
                current = current.right
    return result

# Same tree: 4 -> 2,5; 2 -> 1,3
print(morris_preorder(root))  # [4, 2, 1, 3, 5]