Post-order Traversal of Binary Tree using 1 stack
EasyTrack the last node you emitted
Problem
Return the postorder traversal using a single stack.
Simulate the recursion with a single stack, outputting when both children are done.
The idea
With one stack you must know whether the right subtree has already been processed, so remember the previously emitted node. If it is the current node's right child, both children are done and the node can be recorded.
The trick
- The 'previous' pointer replaces the second stack.
- O(height) space rather than O(n).
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.