Post-order Traversal of Binary Tree using 2 stack
EasyBuild root-right-left, then reverse it
Problem
Return the postorder traversal using two stacks.
Use two stacks: build reverse-postorder in one, pop it into the answer.
The idea
Run a preorder-style walk that pushes left before right, giving root-right-left order, and collect it on a second stack. Popping that second stack reverses the sequence into left-right-root.
The trick
- Postorder is the reverse of a mirrored preorder.
- Simple to write, but uses O(n) extra space for the second stack.
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,null,2,3]
- Output:
- [3, 2, 1]
- Explanation:
- Left, right, node → 3,2,1.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [2, 3, 1]
- Explanation:
- Gives 2,3,1.
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.