Pre, Post, Inorder in one traversal
EasyOne stack, a visit counter per node
Problem
Compute preorder, inorder, and postorder in a single traversal using a state counter per node.
Carry a 'state' (1,2,3) per node on the stack so one walk emits all three orders.
The idea
Push each node with a state number and re-push it with the state incremented: state 1 records preorder and descends left, state 2 records inorder and descends right, state 3 records postorder. One pass produces all three orders.
The trick
- Each node is pushed three times, so it stays O(n).
- The state number is exactly which of the three visits you are on.
Step 1 of 8. Inorder = Left → Node → Right. We dive left first, emit the node, then go right.
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.