Chapter 25: DSA Post-order Traversal
DSA Post-order Traversal – Let’s learn this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the tree step by step, walking through every single move slowly, showing exactly what happens at each moment, and explaining why post-order is different from pre-order and in-order, and when you should actually choose it.
What is Post-order Traversal?
Post-order traversal is one of the three classic depth-first traversals of a binary tree.
The name post-order tells you the rule very clearly:
Post means after → We visit (process/print) the root node after visiting both its subtrees.
So the visiting order is:
Left subtree → Right subtree → Root
The exact sequence you follow is:
- Recursively traverse the left subtree
- Recursively traverse the right subtree
- Visit the current node (process it — print, store, compare, delete, etc.)
Visual Rule – Very easy way to remember
Imagine you are walking around the tree:
|
0 1 2 3 4 5 6 |
Left subtree first ──→ Right subtree next ──→ Visit root last |
Or think of it like this:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
┌───────┐ │ │ ┌──┴────┐ │ │ │ │ Left Right ↑ ↑ Go here first, then here, then ↓ Visit root |
Post-order = “Children first, then root”
Classic Example Tree (same tree we used before)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 |
Post-order traversal of this tree gives:
7 4 8 5 2 9 6 3 1
Let’s see exactly why — step by step.
Step-by-step walkthrough (very detailed)
Start at root = 1
- We first go to left subtree of 1 → node 2
- Go to left of 2 → node 4
- Go to left of 4 → node 7
- 7 has no left
- 7 has no right
- visit 7 → print 7
- backtrack
- 4 has no right
- visit 4 → print 4
- backtrack
- Go to left of 4 → node 7
- Go to right of 2 → node 5
- 5 has no left
- Go to right of 5 → node 8
- 8 has no left
- 8 has no right
- visit 8 → print 8
- backtrack
- visit 5 → print 5
- backtrack
- Now both children of 2 are done
- visit 2 → print 2
- backtrack from 2
- Go to left of 2 → node 4
- Now go to right subtree of root → node 3
- 3 has no left
- Go to right of 3 → node 6
- Go to left of 6 → node 9
- 9 has no left
- 9 has no right
- visit 9 → print 9
- backtrack
- 6 has no right
- visit 6 → print 6
- backtrack
- Go to left of 6 → node 9
- Now both children of 3 are done
- visit 3 → print 3
- backtrack from 3
- Now both children of root are done
- visit root → print 1
Final output: 7 4 8 5 2 9 6 3 1
Post-order Traversal Code (most common interview versions)
1. Recursive (clean and natural)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def postorderTraversal(root): result = [] def helper(node): if not node: return # Step 1: Left subtree first helper(node.left) # Step 2: Right subtree next helper(node.right) # Step 3: Visit root last result.append(node.val) helper(root) return result |
2. Iterative version using Stack (important for interviews)
The iterative post-order is a bit trickier than pre-order or in-order.
Classic method (two stacks or one stack + tracking):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
def postorderTraversal(root): if not root: return [] result = [] stack = [] current = root while current or stack: while current: # Push root and go left stack.append(current) current = current.left # Peek the top temp = stack[-1] # If right subtree exists and not visited yet if temp.right and temp.right != stack[-1] if stack else None: current = temp.right else: # Right is done or doesn't exist → visit now stack.pop() result.append(temp.val) return result |
More common & easier-to-write version (using reverse thinking):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def postorderTraversal(root): if not root: return [] result = [] stack = [root] while stack: node = stack.pop() result.append(node.val) # add to result # Push left first, then right (because we reverse at end) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1] # reverse the result at the end |
This version is easier to remember: It’s like pre-order but we push left before right and reverse the result at the end.
When is Post-order Traversal used? (real applications)
| Use case | Why post-order is perfect |
|---|---|
| Delete a tree / free memory | You must delete children before parent |
| Postfix expression evaluation | Operands come before operator |
| Compute tree size / height / diameter | Need both subtrees computed first |
| Some tree destruction / cleanup operations | Bottom-up processing |
| Generate postfix notation from expression tree | Children first, then operator |
| Bottom-up dynamic programming on trees | Process leaves first, then parents |
Key sentence for interviews:
“Whenever you need to process a node after its children (bottom-up processing), post-order traversal is the natural choice.”
Post-order vs Pre-order vs In-order – Quick Comparison
| Traversal | Visit order | Root position | BST sorted order? | Most famous use case |
|---|---|---|---|---|
| Pre-order | Root → Left → Right | First | No | Copy tree, prefix expr |
| In-order | Left → Root → Right | Middle | Yes | Sorted order, BST validation |
| Post-order | Left → Right → Root | Last | No | Delete tree, postfix expr, bottom-up |
Summary – Post-order Traversal in one line each
- Visit order: Left → Right → Root
- Root is processed after both subtrees
- Recursive version is very clean
- Iterative version is a bit tricky — two common ways: two stacks or reverse pre-order trick
- Time complexity: O(n) — visits every node once
- Space complexity: O(h) recursive / O(n) worst iterative
- Most useful when you need bottom-up processing (children before parent)
- One of the three core DFS traversals you must master fluently
Would you like to continue with any related topic?
Very natural next steps:
- Level Order Traversal (BFS style – the fourth traversal)
- All four traversals (pre/in/post + level-order) on same tree
- Iterative post-order dry run step-by-step
- Post-order applications (delete tree, diameter, postfix evaluation)
- Morris Traversal for post-order (O(1) space – advanced)
- Tree traversals without recursion comparison
Just tell me which direction you want to go next — I’ll explain it with the same level of detail, visuals, and step-by-step clarity! 😊
