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]

The Threading Trick That Bends Time (and Pointers)

Most engineers think Morris Traversal is a party trick. Wrong. It's a production-grade hack that exploits a simple observation: inorder traversal fundamentally needs a way to return to the parent after exhausting the left subtree. Recursion uses the call stack. Iteration uses an explicit stack. Morris says: why not just borrow the right pointer of the rightmost node in the left subtree?

That's the threading. You create a temporary link from the inorder predecessor back to the current node. When you later arrive at that same node through the threaded right pointer, you know the left subtree is fully visited. You break the link and visit the node. This eliminates O(h) space entirely, where h is the height of the tree.

But here's where juniors fold: you must know when to remove the thread. If you forget to cut the temporary link, you'll have a corrupted tree after traversal. The condition is strict — only remove the thread when you re-encounter a node whose left child's rightmost pointer already points back to it. That's the signal: left subtree done, visit now, restore the tree.

// io.thecodeforge — dsa tutorial

public class MorrisInorder {
    static class Node {
        int data;
        Node left, right;
        Node(int val) { this.data = val; }
    }

    public static void inorder(Node root) {
        Node current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.data + " ");
                current = current.right;
            } else {
                Node predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current)
                    predecessor = predecessor.right;

                if (predecessor.right == null) {  // thread not set
                    predecessor.right = current;   // create thread
                    current = current.left;
                } else {                            // thread exists
                    predecessor.right = null;        // cut thread
                    System.out.print(current.data + " ");
                    current = current.right;
                }
            }
        }
    }
}

The One Constraint That Kills Morris in Real Systems

Morris traversal looks elegant on a whiteboard. In production, its most vocal critics are the developers maintaining immutable trees. Threading requires mutation of the tree structure. If your binary tree lives behind an immutable data structure (common in functional programming or event-sourced systems), Morris is dead on arrival.

Even in mutable trees, consider thread safety. If two threads traverse the same tree concurrently, one will yank the thread from under the other's feet. The temporary links are not atomic — you'll get unpredictable results. For read-heavy workloads, stick with the stack-based approach unless you can guarantee single-threaded access or use a read-copy-update pattern.

But here's where Morris shines: embedded systems with tight memory budgets, or interview loops where the interviewer asks for O(1) space traversal. In those constraints, threading is your only hammer. Just don't use it to traverse a tree that another thread is modifying — you'll be debugging a segfault instead of solving the problem.

// io.thecodeforge — dsa tutorial

public class ThreadSafety {
    // NOT thread-safe: two threads on same tree
    static Node root = buildTree();  // shared mutable state
    
    public static void main(String[] args) {
        Runnable task = () -> MorrisInorder.inorder(root);
        Thread t1 = new Thread(task);
        Thread t2 = new Thread(task);
        t1.start();
        t2.start();
        // Expected: race condition on predecessor.right
        // Outcome: missing nodes, loops, or NPE
    }
}