How Post-Order Traversal Works
Post-order traversal visits both subtrees before the node itself. It is the order for anything that has to finish with the children before it can deal with the parent: deleting a tree, sizing directories, evaluating an expression bottom-up.
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
Step 1 of 19
Post-order walk over 7 values, 3 levels deep.
Counters
- Visited
- 0/7
- On the stack
- 0
- Tree height
- 3
- Nodes
- 7
Settings
Post-order
- 1
stack = []; node = root; last = null - 2
while node or stack: - 3
while node: - 4
stack.push(node); node = node.left - 5
top = stack.peek() - 6
if top.right and last != top.right: - 7
node = top.right - 8
else: - 9
visit(top); last = stack.pop()
What each walk is for
| Walk | What you get | Time | Extra space |
|---|---|---|---|
| In-order | Values in sorted order | O(n) | O(h) |
| Pre-order | Root before children, for copying a tree | O(n) | O(h) |
| Post-order | Children before root, for freeing or evaluating | O(n) | O(h) |
| Level-order | Shallowest nodes first, level by level | O(n) | O(w) |
| Search | One value, by comparing at each node | O(h) | O(1) |
n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n — that is what balancing prevents.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n) | O(n) | O(n) | O(h) |
The iterative version needs either two stacks or a 'last visited' marker, because a node must not be emitted the first time it is reached.
How post-order traversal works
Post-order traversal walks the left subtree, then the right, then visits the node. Every child is therefore finished before its parent is touched — which is exactly the constraint when the visit destroys or summarises the node. Freeing a tree in any other order leaves you holding a pointer you have already released; computing a directory's size in any other order means adding up numbers you have not worked out yet.
- If the node is empty, return.
- Traverse the left subtree in full.
- Traverse the right subtree in full.
- Visit the node — both children are already done.
Implementation
The same algorithm the visualiser is running, written to be read.
def post_order(node, visit):
if node is None:
return
post_order(node.left, visit)
post_order(node.right, visit)
visit(node.value) # children are finished by now
def subtree_size(node):
"""Why post-order exists: the parent needs both children's answers."""
if node is None:
return 0
return 1 + subtree_size(node.left) + subtree_size(node.right)When to use it
- Use it to release a tree, in any language where you free memory by hand.
- Use it for bottom-up aggregation: subtree sizes, directory totals, heights, evaluating an expression tree where operands must be computed before the operator.
- Use it for dependency order — a target can only be built once everything it depends on is built, which is post-order over the dependency graph.
Check yourself
If the animation made sense, these should too.
Why must a tree be freed in post-order?
Because the node holds the pointers to its children. Freeing the parent first leaves you with no way to reach the subtrees - or, worse, reading pointers out of memory you have already released.
What makes post-order the natural order for aggregation?
Every child is finished before its parent is visited, so a parent can combine answers that already exist. Subtree sizes, heights, directory totals and expression-tree evaluation all need that guarantee.