Overview
Postorder traversal is a depth-first traversal that visits nodes in the order Left, Right, Root. It fully processes both subtrees before ever touching the node above them.
Visiting children before their parent is exactly what you need when freeing or deleting a tree, or when evaluating an expression tree where operands must be computed before the operator that combines them.
How Postorder Traversal works
- Recursively traverse the entire left subtree.
- Recursively traverse the entire right subtree.
- Visit (process) the current node only after both subtrees are complete.
- Return on an empty subtree (null); every node is visited after all of its descendants.
When to use it
- Safely deleting or freeing a tree, releasing children before the parent that points to them.
- Evaluating an expression tree, computing sub-results before applying each operator.
- Computing bottom-up aggregates such as subtree sizes, heights, or folder sizes.
Complexity analysis
Postorder traversal processes each of the n nodes once, so it runs in O(n) time. The recursion descends to the tree's height h before unwinding, using O(h) space — O(log n) when balanced and O(n) in the degenerate case.
Frequently asked questions
Why is postorder used to delete a tree?
A node's children must be freed before the node itself, otherwise the pointers to those children are lost. Left, Right, Root guarantees each parent is deleted only after its subtrees.
How does postorder evaluate an expression tree?
Leaves hold operands and internal nodes hold operators. Evaluating both children first yields their values, so when a node is visited its operator can be applied immediately — this is postfix (Reverse Polish) evaluation.