The Threading Mechanism & Cycle Detection Without Tag Bits
In a standard binary tree without parent pointers, descending into curr.left destroys our only reference back to curr unless we push curr onto a stack. Notice, however, that in an In-Order traversal, the very last node visited inside curr.left before returning to curr is the in-order predecessor of curr:
$$\text{pred}(u) = \text{rightmost}(u.\text{left})$$
Because $\text{pred}(u)$ is the rightmost node in $u$'s left subtree, its right child pointer is guaranteed to be null in the unmodified tree. Morris Traversal repurposes that exact null slot to store a return address back to $u$. When we later return to $u$ via that thread, how do we know whether we are arriving at $u$ for the first time (from $u$'s parent) or the second time (via the upward thread)? We simply walk down to $\text{pred}(u)$ again:
- Case 1 (First arrival at $u$, $\text{pred}(u).\text{right} == \text{null}$): Install the thread $\text{pred}(u).\text{right} \leftarrow u$ and descend $u \leftarrow u.\text{left}$. (For Pre-Order, emit $u$ right here before descending!)
- Case 2 (Second arrival at $u$, $\text{pred}(u).\text{right} == u$): We have finished $u$'s left subtree. Restore the tree by setting $\text{pred}(u).\text{right} \leftarrow \text{null}$, emit $u$ (for In-Order), and advance $u \leftarrow u.\text{right}$.
| Traversal Method | Total Edge Traversals | Time Complexity | Auxiliary Memory | Mutates Tree During Walk? |
|---|---|---|---|---|
| Morris In-Order / Pre-Order | $\le 4(N - 1)$ edges | O(N) Amortized | O(1) Words | Yes (temporarily; restored on exit) |
| Iterative Explicit Stack | $2(N - 1)$ edges | O(N) | O(h) Words | No (read-only) |
| Static Threaded Tree (Perlis-Thornton) | $2(N - 1)$ edges | O(N) | O(1) Words | No (requires 1 tag bit per pointer) |
Amortized Linearity Proof: Why Predecessor Searches Sum to $O(N)$
Finding $\text{pred}(u)$ walks a right spine of length up to $O(h)$, which naively suggests $O(N h)$ total time. To prove strict $O(N)$ time, count how many times any individual tree edge $e = (x, y)$ is traversed across the entire execution:
- Main pointer
currdescent: Every left edge is traversed at most once downward bycurr = curr.left; every right edge is traversed at most once downward bycurr = curr.right. - Predecessor search spine: Consider the right-leaning chain inside $u.\text{left}$ leading to $\text{pred}(u)$. Crucially, the predecessor search corridors of two distinct nodes $u_1 \ne u_2$ are strictly edge-disjoint! Why? Every edge in $u$'s predecessor path consists of a single left step from $u$ to $u.\text{left}$, followed exclusively by right steps. Thus, walking backward up the right steps and taking one step up-right uniquely identifies $u$.
Because each edge $e$ belongs to the predecessor corridor of at most one ancestor $u$, $e$ is traversed once to set the thread and once to clear the thread. Summing over all $N - 1$ edges bounds total pointer dereferences to at most $4(N - 1) = \Theta(N)$.
Trace how Morris Traversal temporarily rewires each in-order predecessor’s null right pointer (pred.right = curr) to climb back up without a call stack, and how Euler Tour timestamps flatten every subtree into a contiguous array slice [tin[u], tout[u]].
Invariant & State
Visualizing Temporary Thread Creation & Severing
The diagram below illustrates how each node $u$ with a non-empty left child claims a unique, edge-disjoint right spine (highlighted in amber/emerald) leading to its predecessor.
Hardware Reality: Dirty Cache Lines & Read-Only Memory Pages
Although Morris Traversal saves $O(h)$ stack memory, it is often slower in wall-clock latency than an explicit-stack traversal on modern multi-core CPUs for two hardware reasons:
- Cache Line Dirtying (MESI Protocol): Writing
pred->right = currtransitions the 64-byte cache line containingpredfrom Shared (S) to Modified (M), invalidating that cache line across all other CPU cores and forcing write-back traffic upon eviction. - Double Spine Chasing: Every internal node with a left child has its predecessor spine walked twice, doubling pointer-chasing memory accesses compared to an L1-resident explicit array stack.
Implementation: Morris In-Order & Pre-Order in Rust / C++
// C++20: Morris O(1) Auxiliary Space In-Order and Pre-Order Traversals
#include <vector>
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
};
std::vector<int> morrisInorder(Node* root) {
std::vector<int> result;
Node* curr = root;
while (curr != nullptr) {
if (curr->left == nullptr) {
result.push_back(curr->val);
curr = curr->right; // Follows either a real right child or an upward thread!
} else {
// Find the in-order predecessor in curr's left subtree
Node* pred = curr->left;
while (pred->right != nullptr && pred->right != curr) {
pred = pred->right;
}
if (pred->right == nullptr) {
// First arrival at curr: install temporary upward thread
pred->right = curr;
curr = curr->left;
} else {
// Second arrival at curr via thread: restore tree and visit curr
pred->right = nullptr;
result.push_back(curr->val);
curr = curr->right;
}
}
}
return result;
}Failure Modes & Adversarial Pitfalls
- Catastrophic Concurrency Race & Read-Only Pages: Never use Morris Traversal on a concurrently read tree or a tree mapped in read-only memory (
mmap(..., PROT_READ)). Concurrent readers will follow temporary upward threads into infinite loops, and writingpred->right = curron a read-only page triggers an immediate hardware page fault (SIGSEGV). - Early Return / Exception Corruption: If you break out of a Morris Traversal early (e.g., searching for the $k$-th smallest element in a BST) without completing the loop, active threads remain embedded in the tree! This turns the tree into a cyclic graph and causes subsequent destructors (
delete root) to double-free or loop infinitely. Always finish or explicitly unwind active threads before returning.