Morris Inorder Traversal of a Binary Tree
HardThe same threads, recorded later
Problem
Traverse a binary tree in inorder using O(1) extra space with Morris threading.
Thread the tree with temporary links to walk it using no extra stack.
The idea
Identical threading, but record the node when you return through the thread rather than when you create it. That single change converts preorder into inorder while keeping the O(1) space.
The trick
- Record on thread removal, not creation.
- Always undo the thread, or you leave a cycle in the tree.
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,null,2,3] Values: 1, 2, 3.
1if no left: output, go right2else thread predecessor.right to node; go left; unthread on returnInput
- 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, 3, 2]
- Explanation:
- Left, node, right → 1,3,2.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [2, 1, 3]
- Explanation:
- Gives 2,1,3.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty → 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.