Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]

Output: [3,2,1]

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,6,7,5,2,9,8,3,1]

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Approach: Iterative with Two Stacks (Reverse Preorder)

Algorithm

1. Postorder visits the left subtree, then the right subtree, then the root
2. Notice postorder is the reverse of a “root, right, left” preorder-like traversal
3. Push the root onto a stack; pop it and push its value into a second output stack, then push its left and right children (left first so right is processed first)
4. When the first stack is empty, pop everything from the output stack; the values now come out in postorder
5. Alternatively, an iterative version with a visited marker or a single stack can avoid the extra stack

Time & Space Complexity

• Time Complexity: O(n) - every node is processed once
• Space Complexity: O(n) - the two stacks hold up to O(n) nodes in the worst case

Java Implementation

import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;

public class BinaryTreePostorderTraversal {

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        Deque<Integer> output = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.push(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        while (!output.isEmpty()) {
            result.add(output.pop());
        }
        return result;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // Test method
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        System.out.println("Input: root = [1,null,2,3]");
        System.out.println("Output: " + postorderTraversal(root)); // Expected: [3, 2, 1]
    }
}

Recursive Implementation

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

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

Example Walkthrough

For root = [1, null, 2, 3]:

1. Push 1. Pop 1, push value into output, push left (null), push right 2
2. Pop 2, push value into output, push left 3, push right (null)
3. Pop 3, push value into output. Output stack now holds [3, 2, 1] top-down
4. Pop the output stack: result becomes [3, 2, 1]

Key Points

1. Left-Right-Root Order: The root is emitted last among its subtree
2. Reverse Preorder Trick: A “root, right, left” traversal stored on a second stack, when popped, yields postorder
3. Child Push Order: Left is pushed before right so right is popped first in the first stack
4. Single-Stack Alternative: A one-stack solution tracks whether children have been visited
5. O(n) Time: Every node is visited exactly once