1. One-Liner
Iterative postorder (left → right → root) can use two stacks or one stack + reverse of modified preorder (root-right-left then reverse).
2. The Problem It Solves
Postorder is needed for bottom-up work: tree deletion, expression postfix evaluation, computing subtree sums. Iteration avoids deep recursion and matches production tree walkers.
3. The Core Idea
Traverse in root-right-left preorder with a stack (push left after right), collect nodes, then reverse the list to get left-right-root. Alternatively use a second stack to avoid reverse—both are O(n) time.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Start with root on stack. |
| 2 | Pop node; append value to output (temporary order). |
| 3 | Push left, then right (so left processed later in traversal). |
| 4 | Repeat until stack empty. |
| 5 | Reverse output to obtain postorder. |
5. Dry Run Example
Linear tree: 1—2—3 (1 root, right chain).
Traversal collects 1,3,2 in the “root-right-left” pass; reverse → 2,3,1 postorder.
6. Key Properties
| Property | Detail |
|---|---|
| Children before parent | Safe for freeing subtrees |
| Not | Same stack pattern as preorder |
| Alternative | Prev-pointer single stack—harder to code |
7. Where It Is Used
| Domain | Use |
|---|---|
| Memory mgmt | Delete children before parent |
| Compilers | Postfix codegen from expression trees |
8. Interview Tips
Explain why reverse: maps symmetric DFS variant. For strict one-pass postorder without reverse, practice the last visited pointer pattern.
9. Comparison with Other Algorithms
| Approach | Extra space | Clarity |
|---|---|---|
| Reverse preorder trick | O(n) output | Easiest |
| Two explicit stacks | O(n) | Classic textbook |
| One stack + prev | O(h) | Hardest, optimal stack |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n) |
| Space | O(n) for output reverse variant; O(h) possible with advanced one-stack |
Implementation Example (PYTHON)
def postorder_iterative(root):
if not root:
return []
out, stack = [], [root]
while stack:
node = stack.pop()
out.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return out[::-1]