5.15 Binary Tree Postorder Traversal

5.15.1 Problem Metadata

5.15.2 Description

Return the postorder traversal (left-right-root) of a binary tree.

5.15.3 Solution - Iterative Stack

5.15.3.1 Walkthrough

Use a reversed-preorder trick to achieve postorder without two stacks:

  1. Push root.
  2. Pop node, prepend its value (addFirst) to result.
  3. Push left then right children (so right is processed before left).
  4. Prepending reverses the root-right-left traversal into left-right-root.

5.15.3.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) for stack + output list
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    return result;
}

5.15.4 Solution - Recursive

5.15.4.1 Walkthrough

Recursively traverse left subtree, then right subtree, then visit the current node. This mirrors the postorder definition and appends values in left-right-root order.

The recursive approach directly reflects the definition of post-order traversal: 1. Base case: If node is null, return immediately 2. Recurse left: Visit all nodes in the left subtree 3. Recurse right: Visit all nodes in the right subtree 4. Process current: Add current node’s value to result

This is the natural traversal order for deleting trees or performing bottom-up calculations, as children are processed before their parent.

5.15.4.2 Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(h) - Recursion call stack depth where h is tree height (O(n) worst case for skewed tree)

5.15.4.3 Code - Java

public List<Integer> postorderTraversalRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, result);
    return result;
}

private void dfs(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    dfs(node.left, list);
    dfs(node.right, list);
    list.add(node.val);
}