Postorder Traversal
EasyLeft, then right, then root
Problem
Return the postorder traversal (left, right, root) of a binary tree.
Recurse left, recurse right, then visit the node last (Left-Right-Node).
The idea
Both children are fully processed before the node itself, so a node can combine results computed beneath it. That is why postorder underlies heights, subtree sums and any bottom-up computation.
The trick
- Children before parent — required whenever the parent needs their results.
- Also the safe order for deleting or freeing a tree.
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.