Problem Statement
Given the root of a binary tree, return its preorder 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 preorder traversal.
Traversal order:
Root
↓
Left
↓
Right
Recursion naturally remembers the parent nodes.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(H)
Better Approach
Use an explicit stack.
Visit:
Root
↓
Left
↓
Right
Complexity
- Time Complexity: O(N)
- Space Complexity: O(H)
Moving Towards the Optimal Approach
Can we perform preorder traversal without:
Recursion
OR
Stack?
Yes.
Instead of using recursion,
temporarily connect the inorder predecessor back to the current node.
This temporary connection is called a:
Thread
Unlike Morris Inorder,
here we visit the node before moving to the left subtree.
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)
If predecessor’s right is:
NULL
Visit current node.
Create a temporary thread.
Predecessor
↓
Current
Move:
Left
If predecessor already points to current,
remove the thread,
move to the right subtree.
Notice:
Unlike Morris Inorder,
we do not visit the node while removing the thread.
Visualization
Original Tree
4
/
2 5
/
1 3
Temporary Thread
3
4
After returning,
the thread is removed,
restoring the original tree.
Optimal Java Solution
class Solution {
public List<Integer> preorderTraversal(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) {
ans.add(curr.val);
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
curr = curr.right;
}
}
}
return ans;
}
}
Dry Run
Tree
4
/
2 5
/
1 3
Step 1
Current:
4
Visit:
4
Create thread:
3 → 4
Move left.
Step 2
Current:
2
Visit:
2
Create thread:
1 → 2
Move left.
Step 3
Current:
1
No left child.
Visit:
1
Move through thread.
Step 4
Back to:
2
Remove thread.
Move right.
Visit:
3
Return through thread.
Visit:
5
Final Traversal
4
2
1
3
5
Why Morris Preorder Works?
Instead of using recursion,
we temporarily connect:
Inorder Predecessor
↓
Current Node
Since preorder visits the root first,
we process the node when creating the thread.
When we return,
the thread is removed,
and the original tree is restored.
Each edge is traversed at most twice.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(1) |
Interview One-Liner
Morris Preorder Traversal visits the node before creating a temporary thread to its inorder predecessor, achieving preorder traversal in O(1) extra space.
Pattern Learned
Need O(1) Space
↓
No Stack
↓
No Recursion
↓
Thread Binary Tree
↓
Visit Before Going Left
Similar Problems
- Morris Preorder Traversal
- Morris Inorder Traversal
- BST Iterator
- Recover Binary Search Tree
- Binary Tree Traversals
Memory Trick
Think:
Has Left Child?
↓
Find Predecessor
↓
Thread Exists?
↓
No
Visit Node
Create Thread
Go Left
----------------
Yes
Remove Thread
Go Right
Mental Model
Current
↓
Visit
↓
Thread
↓
Left
↓
Back
↓
Right
Whenever you hear:
“Preorder traversal without recursion or stack”
your brain should immediately think:
Morris Preorder Traversal