Post-order traversal

O(n)

Post-order traversal visits a node only after both its subtrees: left, then right, then the node. Since children are processed before their parent, it's used to free/delete a tree safely and to evaluate expression trees (operands before the operator).

Binary search tree

Press ▶ to run

Edit the input and press Play

Loop

How it works

Recurse into the left subtree.
Recurse into the right subtree.
Visit the current node last.
Children are always processed before their parent.

Pseudocode

1postorder(node):                    # O(n)2  if node = null: return3  postorder(node.left)4  postorder(node.right)5  visit(node)                        # children before root