Problem Statement
Given the root of a binary tree, return its inorder traversal.
The challenge is to perform the traversal:
Without Recursion
Without Stack
O(1) Extra Space
Brute Force Intuition
In an interview, you can explain it like this:
Perform a normal recursive inorder traversal.
This naturally follows:
Left
↓
Root
↓
Right
However, recursion uses the system call stack.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(H)
Better Approach
Use an explicit stack.
Traverse:
Go Left
↓
Visit Node
↓
Go Right
Complexity
- Time Complexity: O(N)
- Space Complexity: O(H)
Moving Towards the Optimal Approach
Can we perform inorder traversal without:
Recursion
OR
Stack?
Yes.
The idea is to temporarily modify the tree.
Instead of returning using recursion,
we create a temporary link from the inorder predecessor back to the current node.
This technique is called:
Threading the Binary Tree
Pattern Recognition
Whenever you see:
- Binary Tree Traversal
- O(1) Extra Space
- No Stack
- No Recursion
Think:
Morris Traversal
Key Observation
For every node:
Case 1
No Left Child
Visit it immediately.
Move:
Right
Case 2
Has Left Child
Find its:
Inorder Predecessor
(the rightmost node of the left subtree)
Now:
If predecessor's right is:
NULL
Create a temporary thread.
Predecessor
↓
Current
Move:
Left
If predecessor already points to current,
remove the thread,
visit current,
move right.
Visualization
Original Tree
4
/ \
2 5
/ \
1 3
Temporary Thread
3
\
4
instead of
NULL
Once returned,
remove it again.
Tree becomes unchanged.
Optimal Java Solution
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
ans.add(curr.val);
curr = curr.right;
} else {
TreeNode pred = curr.left;
while (pred.right != null &&
pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
ans.add(curr.val);
curr = curr.right;
}
}
}
return ans;
}
}
Dry Run
Tree
4
/ \
2 5
/ \
1 3
Step 1
Current:
4
Left exists.
Find predecessor:
3
Create thread:
3 → 4
Move left.
Step 2
Current:
2
Find predecessor:
1
Create:
1 → 2
Move left.
Step 3
Current:
1
No left.
Visit:
1
Move via thread.
Step 4
Back to:
2
Remove thread.
Visit:
2
Move right.
Step 5
Visit:
3
Return through thread.
Visit:
4
Visit:
5
Final Traversal
1
2
3
4
5
Why Morris Traversal Works?
Instead of remembering parent nodes using recursion,
we temporarily connect:
Inorder Predecessor
↓
Current Node
This allows us to return after completing the left subtree.
Before leaving,
the temporary connection is removed,
so the original tree remains unchanged.
Each edge is traversed at most twice.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(1) |
Interview One-Liner
Morris Traversal performs inorder traversal in O(1) extra space by temporarily creating threads from each node's inorder predecessor back to the current node.
Pattern Learned
Need O(1) Space
↓
No Stack
↓
No Recursion
↓
Thread Binary Tree
↓
Morris Traversal
Similar Problems
- Morris Inorder Traversal
- Morris Preorder Traversal
- Recover Binary Search Tree
- BST Iterator
- Binary Tree Traversals
Memory Trick
Think:
Has Left Child?
↓
Find Predecessor
↓
Thread Exists?
↓
No
Create Thread
Go Left
----------------
Yes
Remove Thread
Visit Node
Go Right
Mental Model
Current
↓
Left Exists?
↓
Find Rightmost Node
↓
Thread It
↓
Come Back
↓
Remove Thread
↓
Visit
Whenever you hear:
"Traverse a binary tree without recursion or stack"
your brain should immediately think:
Morris Traversal (Threaded Binary Tree)
Top comments (0)