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
Post-order walk over 7 values, 3 levels deep.
Counters
- Visited
- 0/7
- On the stack
- 0
- Tree height
- 3
- Nodes
- 7
Settings
More options
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) |
Scroll the table sideways for the rest of the columns.
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, which is what balancing prevents.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n) | O(n) | O(n) | O(h) |
How post-order traversal works
Post-order traversal walks the left subtree, then the right, then visits the node. Every child is finished before its parent is touched, which is exactly the constraint you have 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
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)