Morris Traversal: The Full Complexity Derivation
If you've read about Morris traversal, you know the headline: O(n) time, O(1) space. But when you look at the code, there's a nested loop. The outer loop iterates over nodes, and for each node with a left child, the inner loop walks along a chain of right pointers to find the in-order predecessor. That inner loop can traverse multiple edges. So why isn't the total time $O(n^2)$?
This page gives you the complete derivation, three different ways, from intuitive to formal. We'll prove both the time and space bounds and show exactly where every unit of work goes.
Space Complexity: O(1)
Let's start with the easier claim. Morris traversal uses only two pointer variables:
TreeNode* cur = root; // current node
TreeNode* pred = nullptr; // predecessor finderThat's it. No stack, no queue, no visited array, no parent pointers, no boolean flags. Two pointers = $O(1)$ auxiliary space, regardless of tree size.
Where Did the Stack Go?
In a standard recursive or iterative in-order traversal, we need an $O(h)$ stack to remember the path from the root to the current node. We push nodes as we go left, and pop them to backtrack. The stack is the mechanism for "going back up" after finishing a left subtree.
Morris replaces the stack with temporary threads. When we're about to go left from node X, instead of pushing X onto a stack, we create a thread: we set X's in-order predecessor's right pointer to X. This thread acts as a "return address." When we later arrive back at the predecessor (having finished the left subtree), we follow the thread back to X.
The crucial observation: the threads are stored in the tree itself, in the right-pointer fields of nodes that originally had null right children. No additional memory is allocated. The tree's own null pointers are temporarily repurposed.
Why There Are Always Enough Null Pointers
A binary tree with $n$ nodes has $n + 1$ null pointers. (Each node has 2 child slots = $2n$ total, and $n - 1$ of them are occupied by edges, leaving $2n - (n-1) = n + 1$ nulls.) Morris only needs to create threads in the right-null-pointer of predecessor nodes. Since every node with a left child has a distinct predecessor, and that predecessor's right pointer is null (it's the rightmost node in the left subtree), there are at most $n/2$ threads created at any point. The null pointers are always available.
Space Complexity Proof
Morris traversal allocates no new data structures. It uses exactly two pointer variables (cur, pred) and modifies existing null pointers in the tree temporarily. All modifications are reversed before the algorithm finishes. Therefore:
Auxiliary space = $O(1)$
Note: this does not count the output (the visited sequence). If you're storing the traversal result, that's $O(n)$ for the output, but the traversal mechanism itself is $O(1)$.
Time Complexity: Why O(n) and Not O(n²)
The algorithm's main loop runs while cur != null. Inside, for each node with a left child, we run a nested loop to find its predecessor. This nested "find predecessor" loop walks a chain of right-child pointers. The question is: across the entire traversal, how many total pointer steps does this inner loop make?
The Naive (Wrong) Analysis
A hasty analysis goes: "The outer loop runs $n$ times, and the inner loop could walk up to $h$ edges each time, so the total is $O(n \cdot h)$, which is $O(n \log n)$ for balanced trees and $O(n^2)$ for skewed trees."
This is wrong because it assumes the inner loop does $O(h)$ work independently for each node. In reality, the inner loop visits a set of edges, and the sets for different nodes don't overlap much. We need to count the total edges traversed across all inner loop executions.
Proof 1: The Edge-Counting Argument
This is the most intuitive proof. We classify every pointer traversal in the algorithm and show that the total is at most $3n$.
The algorithm makes three types of pointer moves:
| Move Type | Code | Description |
|---|---|---|
| DOWN | cur = cur->left or cur = cur->right | Move from a node to one of its children |
| PRED | pred = pred->right (inner loop) | Walk right during predecessor search |
| THREAD | cur = cur->right (via thread) | Follow a thread back up to an ancestor |
Now we bound each type:
Bound 1: DOWN moves ≤ $n - 1$
Each DOWN move follows an actual tree edge (parent to child). The tree has exactly $n - 1$ edges. Each DOWN move uses a distinct edge (we never traverse the same edge downward twice in the entire algorithm, since the outer loop's cur moves monotonically through the in-order sequence). So total DOWN moves $\le n - 1$.
Bound 2: THREAD moves ≤ $n - 1$
Each THREAD move follows a temporary thread from a predecessor back up to some ancestor. A thread is created exactly once (when we first visit a node with a left child) and used exactly once (when we return to that node after finishing its left subtree). So the number of THREAD moves equals the number of nodes with left children, which is at most $n - 1$.
Bound 3: PRED moves ≤ $2(n - 1)$ (the key insight)
This is the non-obvious part. The inner predecessor-search loop walks along right-child edges. Consider a single edge $u \to v$ (where $v$ is the right child of $u$). Can this edge be traversed during multiple predecessor searches?
No. Each right-child edge is traversed in the inner loop at most twice across the entire algorithm: once when creating the thread (first visit to some node X), and once when checking if the thread exists (second visit to X). But these are for the same node X, so the pair (create + check) counts as 2 traversals of each edge, not independent ones.
More precisely: each edge is part of at most one predecessor path. The predecessor of node $X$ is found by going to $X$'s left child and then following right pointers. The set of right-child edges traversed forms a path from $X.left$ to the rightmost node. These paths for different nodes are edge-disjoint, they don't share any right-child edge.
Why disjoint? Because the predecessor paths for different nodes live in different subtrees or different parts of the same subtree, and each right-child edge has only one parent.
Total PRED moves across all predecessor searches $\le 2(n - 1)$ (visiting each edge at most twice: once to create thread, once to detect it).
Summing up:
$$\text{Total moves} = \underbrace{\text{DOWN}}_{\le n-1} + \underbrace{\text{PRED}}_{\le 2(n-1)} + \underbrace{\text{THREAD}}_{\le n-1} \le 4(n-1) = O(n)$$Visualizing Disjoint Predecessor Paths
This is the core of the argument, so let's make it concrete. Consider a tree with 7 nodes:
Proof 2: Potential Method (Formal)
For the formal-minded, here's the potential function argument. Define the potential:
$$\Phi = \text{depth of } \texttt{cur} \text{ in the original tree}$$The depth of cur starts at 0 (root) and ends at... well, cur becomes null when the traversal finishes, so we define the final potential as 0.
For each step of the outer loop, we compute the amortized cost = actual cost + $\Delta\Phi$:
| Case | Actual Cost | $\Delta\Phi$ | Amortized |
|---|---|---|---|
No left child: cur = cur->right | $O(1)$ | Varies ($\le +1$ or $\le -h$) | Accounted by construction |
| Left child, first visit: find pred ($k$ steps) + go left | $O(k)$ | $+1$ (went one level deeper) | $O(k + 1)$ |
| Left child, second visit: find pred ($k$ steps) + go right | $O(k)$ | Decreases by $k$ (thread back up) | $O(k) - k = O(1)$ |
The key: the $k$ edges walked downward during first-visit predecessor searches increase the potential. On the second visit, following the thread back up decreases the potential by the same amount, paying for the work. Each edge contributes at most a constant to the amortized total.
Summing over all $n$ iterations, the total amortized cost is $O(n)$, and since $\Phi$ starts and ends at 0, the actual total cost equals the amortized total: $O(n)$.
Proof 3: The Intuitive Argument
If the formal proofs feel opaque, here's the simplest way to see it:
Every node is visited at most 3 times:
- When
curfirst arrives at the node (from its parent or via a thread). - When the predecessor search passes through the node (at most once, since predecessor paths are disjoint).
- When
curarrives at the node a second time (via the thread, for nodes with left children).
Three visits per node. $n$ nodes. Total work: $3n = O(n)$.
Animation: Counting Edge Traversals
Click Step to advance Morris in-order traversal on a 6-node tree. Watch the counters for each type of pointer move. At the end, verify the total is linear.
▶ Morris Edge-Count Tracker
Worst and Best Cases
Best Case: Right-Skewed Tree
If every node has only a right child, no node has a left child, so the inner loop never runs. Morris degenerates to a simple sequential walk: $n$ steps, zero predecessor searches. Total: exactly $n$ pointer moves.
Worst Case: Left-Skewed Tree
If every node has only a left child (a left-skewed chain), every node triggers a predecessor search. But the predecessor searches are trivially short: go to the left child, it has no right child, so the predecessor is immediately found (1 step). Total predecessor-search steps: $n - 1$ (one per node except the leaf). Add $n$ outer-loop iterations. Total: $\approx 2n$.
Balanced Tree
In a balanced tree, predecessor paths can be longer (up to $O(\log n)$ for the root's predecessor). But the paths are disjoint, and they partition the tree's edges among themselves. The total is still $O(n)$.
Complexity Comparison
| Approach | Time | Space (auxiliary) | Modifies Tree? |
|---|---|---|---|
| Recursive traversal | $O(n)$ | $O(h)$ call stack | No |
| Iterative with stack | $O(n)$ | $O(h)$ explicit stack | No |
| Threaded tree traversal | $O(n)$ | $O(1)$ | No (pre-built) |
| Morris traversal | $O(n)$ | $O(1)$ | Yes (temporary) |
Where $h$ is the height: $O(\log n)$ for balanced, $O(n)$ for skewed.
Summary
- Space: $O(1)$. Only two pointers. Threads stored in existing null slots.
- Time: $O(n)$. Three types of pointer moves (DOWN, PRED, THREAD), each type totals at most $O(n)$ across the entire algorithm.
- The inner predecessor-search loop is not $O(h)$ per node. Predecessor paths are edge-disjoint, so the total across all searches is $O(n)$.
- The constant factor is at most ~3x compared to simple recursive traversal (which also does $\Theta(n)$ pointer moves). In practice the overhead is small.