Preorder Traversal
Visits the root first, then recursively traverses left and right subtrees.
Recursively traverses left and right subtrees, then visits the root last.
Postorder traversal visits each node in a binary tree in the order: left subtree, right subtree, root. The root is always processed last, after all of its descendants have been visited. This "children first, parent last" property makes postorder traversal the natural choice for any computation that depends on results from a node's subtrees. The name "postorder" reflects that the current node is processed after (post-) its children.
For a tree with root A, left child B (with children D and E), and right child C (with children F and G), postorder visits: D, E, B, F, G, C, A. Notice that the root A is the very last node visited. Leaves are visited first because they have no children to process, and internal nodes are visited only after all their descendants have been handled.
The recursive implementation naturally ensures children are processed before their parent. An iterative version is slightly trickier than preorder or inorder. One common approach uses two stacks: push the root onto the first stack, then repeatedly pop a node, push it onto the second stack, and push its left and right children onto the first stack. The second stack, read from top to bottom, gives the postorder sequence. Alternatively, a modified single-stack approach tracks whether a node's right subtree has already been visited before processing the node.
| Case | Time | Space |
|---|---|---|
| All cases | O(n) | O(h) where h = tree height |
Like all depth-first traversals, postorder visits each node exactly once in O(n) time. The space complexity is O(h) for the call stack or explicit stack, where h is the tree height -- O(log n) for balanced trees and O(n) for skewed trees.
Postorder traversal is uniquely suited for computing properties that aggregate information from subtrees upward. To compute the height of a tree, you need the heights of the left and right subtrees before you can determine the height of the current node: height(node) = 1 + max(height(left), height(right)). Postorder naturally provides this because both children are fully processed before the parent. The same applies to computing subtree sums, subtree sizes, diameter calculations, and checking whether a tree is balanced.
When deleting an entire tree or freeing memory in languages without garbage collection (such as C or C++), postorder traversal is essential. You must delete children before their parent because deleting a parent first would lose the references to its children, causing memory leaks. Postorder ensures every child is freed before its parent, making it the safe traversal order for destruction.
In expression trees, postorder traversal produces postfix notation, also known as Reverse Polish Notation (RPN). For the expression (3 + 5) * 2, postorder yields: 3 5 + 2 *. RPN was popularized by Hewlett-Packard calculators in the 1960s and 1970s and is still used in some scientific calculators and stack-based programming languages like Forth. RPN is evaluated directly using a stack: read tokens left to right, push operands, and when you encounter an operator, pop the required operands, apply the operator, and push the result.
Compilers use postorder traversal extensively when generating code from abstract syntax trees (ASTs). In a syntax tree for an expression, you must evaluate operands before applying the operator, which is exactly what postorder provides. Many code generation passes in compilers walk the AST in postorder to emit instructions for children before combining them at the parent node. This pattern extends beyond arithmetic to assignment statements, function calls, and control flow constructs.
Choose postorder traversal when you need to process children before their parent. Common scenarios include safe tree deletion, computing aggregate subtree properties (height, size, sum, balance factor), generating postfix expressions, and compiler code generation. If you need to process parents first, use preorder. If you need sorted output from a BST, use inorder.