Traversal

Post-Order (Left, Right, Root)

Traverse both subtrees first, then visit the root last. Useful when you need to process children before the parent — like calculating directory sizes or deleting a tree bottom-up.

O(n)

O(h)

How It Works

Post-order traversal handles both subtrees before the node itself: recurse left, recurse right, then process the root. That ordering means a node runs only after complete information about its children is available, making it the backbone of bottom-up computations — subtree sizes, heights, directory disk usage, safely deleting a tree, or evaluating expression trees where operands must be computed before the operator.

A common iterative trick is to run a modified pre-order (root, right, left) and reverse the output, or to track the last-visited node so you know when a subtree is finished. Either way, each node is processed once for O(n) time, with O(h) stack space. The power is not asymptotic speed but correctness: any computation where a parent's answer depends on its children's answers is inherently post-order.

Step-by-Step Visualization

Post-order: Left, Right, Root

Visit leaves first4

Output[4]

1/3

Code

Java

static List<Integer> postorder(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);

  while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    if (node == null) continue;
    result.add(node.val);
    stack.push(node.left);
    stack.push(node.right);
  }
  Collections.reverse(result);
  return result;
}

// Tree: [1,2,3,4,5] → Post-order: [4,5,2,3,1]

Tips & Gotchas

1Visit left subtree, right subtree, then root (children before parent)

2Useful for deletion, calculating subtree sizes, expression trees

3Trick: reverse of modified pre-order (root, right, left)

Practice Problems

1Binary Tree Postorder Traversal
2Delete Nodes and Return Forest
3Evaluate Reverse Polish Notation
4Find Duplicate Subtrees
5Binary Tree Maximum Path Sum

About the Traversal Pattern

There are four ways to visit every node in a tree. Three use DFS (going deep before going wide) with different orderings, and one uses BFS (going wide before going deep). Each ordering is useful for different problems.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

When is post-order required rather than just convenient?

Whenever the parent's result is a function of its children's results — computing heights, pruning empty subtrees, or freeing memory where children must be released before the parent. Visiting the root first would mean acting before the needed child answers exist.

Why is iterative post-order considered the trickiest of the three DFS orders?

With one stack, a node must be popped only after both subtrees finish, which requires either a last-visited pointer or a peek-twice pattern. The reverse-of-modified-pre-order trick sidesteps this: emit root-right-left with a normal stack, then reverse the result.