Morris Traversal
The Problem That Shouldn't Be Solvable
Every traversal you've seen so far uses extra space proportional to the tree's height: \(O(h)\) for the explicit stack, \(O(h)\) for the call stack. That space stores return addresses — when you go left, you need to remember where to come back to.
Here's the challenge: perform an inorder traversal using \(O(1)\) extra space. No stack. No recursion. No parent pointers.
Think about why this seems impossible. When you're at node 4 (bottom-left) and you're done, how do you get back to node 2? Without a stack, there's no record of how you got here. Without a parent pointer, node 4 doesn't know node 2 exists.
Morris traversal solves this by temporarily modifying the tree itself. It creates and removes temporary pointers — called threads — that act as return addresses woven directly into the tree structure.
The Tree
Expected inorder: [4, 2, 5, 1, 6, 3, 7].
The Core Idea: Threading
When you're about to go left from some node — call it current — you'll eventually need to come back. In inorder traversal, you come back to current after visiting everything in its left subtree. The last node visited in the left subtree (before returning to current) is the inorder predecessor: the rightmost node in current's left subtree.
That predecessor's right child is currently nullptr — it has no right subtree. Morris traversal temporarily sets predecessor->right = current. This creates a thread — a temporary right pointer that leads back to current.
Later, when you follow the thread back to current, you detect it (the predecessor's right points to current instead of being nullptr), remove it to restore the tree, and continue.
A thread is a temporary right pointer from a node's inorder predecessor back to the node itself. It serves as a return address, eliminating the need for a stack.
The Algorithm, Step by Step
Set current = root. Repeat until current is null:
Case 1: current has no left child.
You can't go left, so current IS the next node in inorder. Process it. Move right: current = current->right.
Case 2: current has a left child.
Find the inorder predecessor: start at current->left, then go right as far as possible (stop if you reach nullptr or loop back to current).
- Sub-case 2a: Predecessor's right is
nullptr. You haven't visited the left subtree yet. Create the thread:predecessor->right = current. Now go left:current = current->left. - Sub-case 2b: Predecessor's right is
current. You've come back via the thread. The left subtree is done. Remove the thread:predecessor->right = nullptr. Processcurrent. Move right:current = current->right.
That's the entire algorithm. Two cases, two sub-cases.
The Code
vector<int> morrisInorder(Node* root) {
vector<int> result;
Node* current = root;
while (current) {
if (!current->left) {
result.push_back(current->value);
current = current->right;
} else {
Node* predecessor = current->left;
while (predecessor->right && predecessor->right != current) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
result.push_back(current->value);
current = current->right;
}
}
}
return result;
}
Full Trace With Tree Diagrams
This trace is long because you need to see the threads being created and removed. Follow every step.
Step 1: current = 1
Node 1 has a left child. Find predecessor: start at 2, go right to 5. Node 5's right is nullptr.
Sub-case 2a: Create thread: 5->right = 1. Go left.
(The arrow from 5 to 1 is the thread. Shown as 5→ with note.)
current = 2
Step 2: current = 2
Node 2 has a left child. Find predecessor: start at 4. Node 4's right is nullptr.
Sub-case 2a: Create thread: 4->right = 2. Go left.
current = 4
Step 3: current = 4
Node 4 has no left child.
Case 1: Process 4. Move right: current = 4->right = 2 (following the thread!).
Result: [4]
Step 4: current = 2
Node 2 has a left child. Find predecessor: start at 4, go right... 4->right = 2 = current.
Sub-case 2b: Thread detected. Remove thread: 4->right = nullptr. Process 2. Move right.
Result: [4, 2]
current = 5
Step 5: current = 5
Node 5 has no left child.
Case 1: Process 5. Move right: current = 5->right = 1 (following the thread!).
Result: [4, 2, 5]
Step 6: current = 1
Node 1 has a left child. Find predecessor: start at 2, go right to 5, 5->right = 1 = current.
Sub-case 2b: Thread detected. Remove thread: 5->right = nullptr. Process 1. Move right.
Tree fully restored on the left side.
Result: [4, 2, 5, 1]
current = 3
Step 7: current = 3
Node 3 has a left child. Find predecessor: start at 6. Node 6's right is nullptr.
Sub-case 2a: Create thread: 6->right = 3. Go left.
current = 6
Step 8: current = 6
Node 6 has no left child.
Case 1: Process 6. Move right: current = 6->right = 3 (following the thread).
Result: [4, 2, 5, 1, 6]
Step 9: current = 3
Node 3 has a left child. Find predecessor: start at 6, 6->right = 3 = current.
Sub-case 2b: Thread detected. Remove thread: 6->right = nullptr. Process 3. Move right.
Result: [4, 2, 5, 1, 6, 3]
current = 7
Step 10: current = 7
Node 7 has no left child.
Case 1: Process 7. Move right: current = 7->right = nullptr.
Result: [4, 2, 5, 1, 6, 3, 7]
current = nullptr, loop ends. Tree is fully restored.
Trace Summary Table
| Step | current | Case | Thread Action | Process | Tree Modified? |
|---|---|---|---|---|---|
| 1 | 1 | 2a | Create 5→1 | — | Yes |
| 2 | 2 | 2a | Create 4→2 | — | Yes |
| 3 | 4 | 1 | Follow 4→2 | 4 | No |
| 4 | 2 | 2b | Remove 4→2 | 2 | Restored |
| 5 | 5 | 1 | Follow 5→1 | 5 | No |
| 6 | 1 | 2b | Remove 5→1 | 1 | Restored |
| 7 | 3 | 2a | Create 6→3 | — | Yes |
| 8 | 6 | 1 | Follow 6→3 | 6 | No |
| 9 | 3 | 2b | Remove 6→3 | 3 | Restored |
| 10 | 7 | 1 | — | 7 | No |
Every thread that gets created also gets removed. The tree ends in its original state.
Morris Preorder
The preorder variant is almost identical. The only difference: you process the node at sub-case 2a (when you first arrive and create the thread) instead of at sub-case 2b (when you come back).
vector<int> morrisPreorder(Node* root) {
vector<int> result;
Node* current = root;
while (current) {
if (!current->left) {
result.push_back(current->value);
current = current->right;
} else {
Node* predecessor = current->left;
while (predecessor->right && predecessor->right != current) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
result.push_back(current->value);
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
current = current->right;
}
}
}
return result;
}
Compare the two versions: the result.push_back line moved from sub-case 2b to sub-case 2a. That's the only change.
Complexity
- Time: \(O(n)\). This isn't obvious — the predecessor-finding inner loop looks like it could be \(O(n)\) per step. But across the entire traversal, every edge is traversed at most twice (once to find the predecessor, once to follow the thread back). Total edge traversals: \(O(n)\).
- Space: \(O(1)\) extra. No stack, no recursion. The output array is \(O(n)\), but that's the output, not auxiliary space.
When to Use Morris
| Situation | Use Morris? |
|---|---|
| Need \(O(1)\) extra space for traversal | Yes — this is the only way |
| Read-only iteration over a BST (e.g., find \(k\)-th element) | Yes — ideal |
| Tree must not be modified (e.g., concurrent access) | No — Morris temporarily modifies the tree |
| Need the stack for additional state (e.g., path tracking) | No — there is no stack |
| Need postorder | Possible but complex — not recommended |
| Typical interview/contest problem | Rarely — \(O(h)\) stack space is almost always fine |
Morris traversal trades tree modification for stack elimination. Use it when space is the bottleneck and you can tolerate temporary structural changes.
Connection to Threaded Binary Trees
Morris traversal creates and removes threads dynamically. But what if you kept the threads permanently?
A threaded binary tree is a tree where every null right pointer is replaced by a thread to the node's inorder successor. Every null left pointer can similarly thread to the inorder predecessor.
In a threaded binary tree, inorder traversal is always \(O(n)\) time and \(O(1)\) space — you just follow right pointers, some of which are real children and some are threads. A one-bit flag on each node distinguishes threads from real children.
Morris traversal is essentially building a threaded binary tree on the fly, using it, and then dismantling it. Threaded binary trees make this permanent, which is useful when you need to traverse the tree many times without extra space.
This is a rare data structure in practice — parent pointers are simpler and more flexible. But the concept illuminates why Morris works: threading is a general idea, and Morris is its temporary, on-the-fly application.
Try It
The starter code has a morrisInorder function with a TODO. Fill it in and verify:
Predict before running: After step 2 in the trace, two threads exist (4→2 and 5→1). If you ran a naive recursive inorder at this point, would it loop forever? Yes — the thread from 5 to 1 creates a cycle. Morris traversal detects these cycles (predecessor's right == current) and removes them. That detection is what makes the algorithm work.
Challenge: Modify Morris inorder to find the \(k\)-th smallest element in a BST. Stop as soon as you've processed \(k\) nodes. Make sure you restore any remaining threads before returning — otherwise you'll leave the tree corrupted.
Challenge 2: Implement Morris preorder. The only change from inorder is where you place the process line. Verify it produces [1, 2, 4, 5, 3, 6, 7].
Edge Cases to Watch For
- Tree must not be read-only: Morris temporarily modifies the tree. If another thread is reading the tree concurrently, it will see corrupted pointers. Never use Morris on shared, read-only data structures.
- Early termination (k-th smallest): If you stop Morris traversal early, you must clean up any remaining threads. Otherwise the tree is left in a corrupted state with dangling backward pointers.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 94 — Binary Tree Inorder Traversal | leetcode.com/problems/binary-tree-inorder-traversal | Easy |
| LC 99 — Recover Binary Search Tree | leetcode.com/problems/recover-binary-search-tree | Medium |
| LC 501 — Find Mode in Binary Search Tree | leetcode.com/problems/find-mode-in-binary-search-tree | Easy |
| LC 230 — Kth Smallest Element in a BST | leetcode.com/problems/kth-smallest-element-in-a-bst | Medium |
| LC 314 — Vertical Order Traversal | leetcode.com/problems/binary-tree-vertical-order-traversal | Medium |
| LC 987 — Vertical Order Traversal II | leetcode.com/problems/vertical-order-traversal-of-a-binary-tree | Hard |
| LC 429 — N-ary Tree Level Order | leetcode.com/problems/n-ary-tree-level-order-traversal | Medium |
What's Next?
You can now traverse a tree in every possible way. The next question: what do you DO during the traversal? Chapter 3 teaches the most powerful pattern — collecting information from children and combining it at the parent.