Morris Traversal — In-Order Tree Traversal in O(1) Space

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]

Frequently Asked Questions