Morris Traversal
Traverse a tree using O(1) extra space (no stack, no recursion) by temporarily threading the tree — making the rightmost node of the left subtree point back to the current node. After visiting, undo the thread.
How It Works
Morris traversal achieves in-order traversal with O(1) extra space by temporarily rewiring the tree instead of using a stack or recursion. At each node with a left child, it finds the left subtree's rightmost node (the in-order predecessor) and threads that node's null right pointer back to the current node. The traversal then descends left; when it later climbs back up along the thread, it detects the existing link, removes it to restore the tree, visits the node, and moves right.
Each edge is walked at most a constant number of times — once going down and once or twice while locating predecessors — so time remains O(n) despite the extra predecessor searches. The payoff is space: standard DFS needs O(h) memory, but Morris needs only a couple of pointers, which matters for very deep trees or memory-constrained environments. A pre-order variant exists by visiting the node before descending left.
Step-by-Step Visualization
Code
static List<Integer> morrisInorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
result.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; // Create thread
curr = curr.left;
} else {
pred.right = null; // Remove thread
result.add(curr.val);
curr = curr.right;
}
}
}
return result;
}Tips & Gotchas
Practice Problems
- 1Binary Tree Inorder Traversal
- 2Recover Binary Search Tree
- 3Kth Smallest Element in a BST
- 4Convert Binary Search Tree to Sorted Doubly Linked List
About the Traversal Pattern
There are four ways to visit every node in a tree. Three use DFS (going deep before going wide) with different orderings, and one uses BFS (going wide before going deep). Each ordering is useful for different problems.
Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.
Common Trees Interview Problems
- Maximum Depth of Binary Tree
- Validate BST
- Binary Tree Level Order Traversal
- Lowest Common Ancestor
- Serialize and Deserialize Binary Tree
- Diameter of Binary Tree
Frequently Asked Questions
Is Morris traversal safe if other code reads the tree concurrently?
No. Morris mutates right pointers mid-traversal and only restores them afterward, so a concurrent reader could see threaded links and follow a cycle. Use it only when you have exclusive access to the tree during the walk.
Doesn't repeatedly searching for predecessors make it slower than O(n)?
It stays O(n) because each predecessor search walks edges along the right spine of a left subtree, and every edge in the tree is traversed only a constant number of times across the whole algorithm. The constant factor is higher than stack-based DFS, but the asymptotic bound is identical.
When is Morris worth the added complexity over recursion?
Mainly when O(1) auxiliary space is an explicit requirement, such as Recover Binary Search Tree's follow-up, or when trees are deep enough that an O(h) stack risks overflow. For everyday problems, recursive or stack-based traversal is simpler and equally fast.