Preorder, Inorder, and Postorder Traversal in one Traversal
EasyThe same three-state stack walk
Problem
Produce all three traversals (pre, in, post) in one pass using a stack of (node, state).
Carry a 'state' (1,2,3) per node on the stack so one walk emits all three orders.
The idea
Carry a (node, state) pair on the stack. Incrementing the state on each pop tells you which list to append to and which child to descend into, so the three traversals fall out of a single loop.
The trick
- State 1 -> preorder + go left, 2 -> inorder + go right, 3 -> postorder + pop.
- O(n) time and O(height) space.
Step 1 of 8. Inorder = Left → Node → Right. We dive left first, emit the node, then go right.
1/8
Optimal
timeO(n)spaceO(h)
Order = when you emit the node.
1function inorder(node) {2 if (!node) return;3 inorder(node.left);4 visit(node.val); // node between children5 inorder(node.right);6}Input
- nodes
- 6, 5 edges
Output
- output
- —
- inorder
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,3,4,5]
- Output:
- [[1, 2, 4, 5, 3], [4, 2, 5, 1, 3], [4, 5, 2, 3, 1]]
- Explanation:
- Get pre, in and post orders together.
Example 2
- Input:
- tree = [1]
- Output:
- [[1], [1], [1]]
- Explanation:
- All three are just [1].
Example 3
- Input:
- tree = [1,2]
- Output:
- [[1, 2], [2, 1], [2, 1]]
- Explanation:
- One traversal, three outputs.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.