Morris Preorder Traversal of a Binary Tree
HardThread the tree instead of using a stack
Problem
Traverse a binary tree in preorder using O(1) extra space with Morris threading.
Thread the tree with temporary links to walk it using no extra stack.
The idea
For a node with a left child, find that subtree's rightmost node and temporarily point it back at the current node — a thread you follow to return. Recording the node before descending gives preorder in O(1) space.
The trick
- Record the node when you create the thread, on the way down.
- Remove the thread when you come back through it, restoring the tree.
- O(n) time, O(1) space; each edge is walked at most twice.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,3] Values: 1, 2, 3.
1at each node with a left child: find predecessor; thread it; output node before going leftInput
- array
- [1, 2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,null,2,3]
- Output:
- [1, 2, 3]
- Explanation:
- Root, then left subtree, then right → 1,2,3.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [1, 2, 3]
- Explanation:
- Visit 1, then 2, then 3.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty tree → nothing.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.