A tree traversal method that visits nodes in the order: left child, right child, root. It is used to delete the tree.
1 2 3 4 5 6 7 8 9 10 11 12
{
"status": "starting traversal"
}Overview
Post-order traversal visits the left subtree, then the right subtree, and only then the node itself. Every node is processed after all of its descendants, so information flows from the leaves up to the root.
That bottom-up order is what you need when a parent depends on results from its children: computing the height or size of a tree, evaluating an arithmetic expression tree, or freeing memory (you must delete the children before the parent that points to them).
On the default tree, post-order visits 2, 7, 5, 12, 18, 15, 10. The root, 10, comes last, and each subtree root (5 and 15) appears right after its own children.
Step by step
- If the current node is null, return.
- Recursively traverse the left subtree.
- Recursively traverse the right subtree.
- Visit the current node.
Complexity
| Case | Cost | Why |
|---|---|---|
| Time | O(n) | Each node is visited once. |
| Space (balanced tree) | O(log n) | Recursion depth equals tree height. |
| Space (skewed tree) | O(n) | Height can be n. |
When to use it
- Deleting or freeing a tree safely.
- Evaluating expression trees (it produces postfix / Reverse Polish notation).
- Any 'combine the children's answers' computation: height, subtree sums, diameter, checking balance.
Common mistakes
- The iterative version is the trickiest of the three depth-first traversals; a common trick is to do a modified pre-order (node, right, left) and reverse the result.
- Mixing up post-order with reverse pre-order: they are not the same sequence.
- Deep recursion can overflow the call stack on skewed trees.
A dry run is the best way to check your understanding of Post-order Traversal: follow each row, predict the next one, and compare. The run below takes 60 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- Binary tree (see the input box above)
- Result
- final_path = [2, 7, 5, 12, 18, 15, 10]
| Step | Line | What happens |
|---|---|---|
| 1 | 1 | status = starting traversal |
| 3 | 4 | from_node = 10, action = traversing left |
| 5 | 4 | from_node = 5, action = traversing left |
| 7 | 4 | from_node = 2, action = traversing left |
| 9 | 3 | node = is null, action = return |
| 10 | 5 | from_node = 2, action = traversing right |
| 12 | 3 | node = is null, action = return |
| 13 | 8 | current_node = 2, action = visiting node |
| 15 | 11 | finished_subtree_at = 2, action = return |
| 16 | 5 | from_node = 5, action = traversing right |
| 18 | 4 | from_node = 7, action = traversing left |
| 20 | 3 | node = is null, action = return |
| 21 | 5 | from_node = 7, action = traversing right |
| 23 | 3 | node = is null, action = return |
| 24 | 8 | current_node = 7, action = visiting node |
| 26 | 11 | finished_subtree_at = 7, action = return |
| 27 | 8 | current_node = 5, action = visiting node |
| 29 | 11 | finished_subtree_at = 5, action = return |
| 30 | 5 | from_node = 10, action = traversing right |
| 32 | 4 | from_node = 15, action = traversing left |
| 34 | 4 | from_node = 12, action = traversing left |
| 36 | 3 | node = is null, action = return |
| 37 | 5 | from_node = 12, action = traversing right |
| 39 | 3 | node = is null, action = return |
| 40 | 8 | current_node = 12, action = visiting node |
| 42 | 11 | finished_subtree_at = 12, action = return |
| 43 | 5 | from_node = 15, action = traversing right |
| 45 | 4 | from_node = 18, action = traversing left |
| 47 | 3 | node = is null, action = return |
| 48 | 5 | from_node = 18, action = traversing right |
| 50 | 3 | node = is null, action = return |
| 51 | 8 | current_node = 18, action = visiting node |
| 53 | 11 | finished_subtree_at = 18, action = return |
| 54 | 8 | current_node = 15, action = visiting node |
| 56 | 11 | finished_subtree_at = 15, action = return |
| 57 | 8 | current_node = 10, action = visiting node |
| 59 | 11 | finished_subtree_at = 10, action = return |
| 60 | 14 | final_path = [2, 7, 5, 12, 18, 15, 10] |