☕ DSA Java Articles

Topics › Binary Trees › Traversals

Postorder Traversal

Easy TUF ID 135 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return the values of its nodes in postorder: first the entire left subtree in postorder, then the entire right subtree in postorder, and only then the node itself. An empty tree has an empty traversal.

Constraints: between 0 and 10^5 nodes here (LeetCode uses at most 100), arbitrary 32-bit values, duplicates allowed.

Trees are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

    1
     \
      2
     /
    3
root = [1, null, 2, 3]
answer = [3, 2, 1]       // 3 is finished first, then 2 (its subtree is done), then the root

Example 2

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
root = [1, 2, 3, 4, 5, 6, 7]
answer = [4, 5, 2, 6, 7, 3, 1]   // every node appears after all of its descendants; the root is last

Postorder is the order to use whenever a node’s answer depends on its children’s answers: computing heights and sizes, freeing or deleting a tree, evaluating an expression tree. By the time a node is processed, both of its subtrees have already been handled.

Approach 1: Recursion

Intuition. The definition is recursive, so the code is too: traverse the left subtree, traverse the right subtree, then record the node. One shared list collects the output so that no call has to build and concatenate its own list.

Algorithm.

  1. If the node is null, return.
  2. Traverse the left subtree, then the right subtree.
  3. Append the node’s value.
static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    postorder(root, out);
    return out;
}

private static void postorder(TreeNode node, List<Integer> out) {
    if (node == null) return;                 // empty subtree: nothing to visit
    postorder(node.left, out);                // Left
    postorder(node.right, out);               // Right
    out.add(node.val);                        // Root, only after both subtrees are finished
}

Why it works. By induction on the subtree size: the first two calls append exactly the left and right subtrees in postorder, and the node is appended after both, which is the definition.

Complexity. Time O(n): constant work per node plus n + 1 calls on null children. Space O(h) for the call stack, which becomes O(n) on a chain; a chain of 10^5 nodes can overflow Java’s default stack.

Postorder is the hardest of the three orders to make iterative, because a node is passed twice before it can be emitted: once on the way down into its left subtree and once on the way from the left subtree into the right subtree. The next two approaches handle that in two different ways.

Approach 2: Reverse a modified preorder

Intuition. Write postorder backwards: Left, Right, Root reversed is Root, Right, Left. That is just preorder with the two children swapped, and preorder is easy with a stack because a node can be emitted the moment it is popped. So we generate Root, Right, Left with a stack (pushing the left child first so the right child is popped first), then reverse the list.

Why the reversal is exact and not just “roughly right”: by induction, the stack walk emits the root, then the right subtree in Root-Right-Left order, then the left subtree in Root-Right-Left order. Reversing a concatenation reverses the order of the pieces and reverses each piece, which gives the left subtree in postorder, the right subtree in postorder, then the root.

Algorithm.

  1. If the root is null, return an empty list.
  2. Push the root. While the stack is not empty: pop a node, append it, push its left child, then its right child (each only if present).
  3. Reverse the list.
static List<Integer> reversedPreorder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);                                // builds Root, Right, Left
        if (node.left != null) stack.push(node.left);     // left pushed first so right is popped first
        if (node.right != null) stack.push(node.right);
    }
    Collections.reverse(out);                             // reverse of Root-Right-Left is Left-Right-Root
    return out;
}

On Example 2 the stack walk produces [1, 3, 7, 6, 2, 5, 4], and reversing gives [4, 5, 2, 6, 7, 3, 1].

Complexity. Time O(n): one push and one pop per node, and the reversal is linear. Space O(h) for the stack, but the method cannot hand out any value until the whole traversal is done, because the first postorder value is the last one generated. When that matters (streaming, or stopping early), use Approach 3. The classic “two stacks” formulation of this same idea uses a second stack in place of the reversal.

Approach 3: One stack with a last-visited pointer

Intuition. Use the same stack shape as iterative inorder: walk left, pushing every node. When we cannot go further left, look at (but do not pop) the top node. Its left subtree is done. Two cases remain:

The node alone cannot tell us which case we are in. The trick is to remember the last node we emitted. In postorder the root of a subtree is the last node of that subtree to be emitted, so if top.right == lastVisited, we have just come back from the right subtree.

Algorithm.

  1. Set cur = root, lastVisited = null.
  2. While cur is not null or the stack is not empty:
    • Walk left from cur, pushing every node.
    • Peek at top. If top.right exists and is not lastVisited, set cur = top.right.
    • Otherwise append top, pop it, and set lastVisited to it.
static List<Integer> oneStack(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root, lastVisited = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {                             // go as far left as possible
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.peek();                      // its left subtree is finished
        if (top.right != null && top.right != lastVisited) {
            cur = top.right;                              // right subtree not done yet: go there first
        } else {
            out.add(top.val);                             // both subtrees done: emit and retire it
            lastVisited = stack.pop();
        }
    }
    return out;
}

Dry run on Example 1 (1 -> right 2 -> left 3). The stack is written bottom to top.

Step Stack top Decision Output
1 [1] 1 right child 2 is not lastVisited (null): go right  
2 [1, 2, 3] 3 pushed 2 and 3 walking left; 3 has no right child: emit 3
3 [1, 2] 2 no right child: emit 3 2
4 [1] 1 right child 2 equals lastVisited: emit 3 2 1

Without lastVisited, step 4 would send us into node 2’s subtree a second time and the loop would never end.

Complexity. Time O(n): each node is pushed once, popped once, and peeked at most twice. Space O(h) for the stack, and values are produced in final order as the walk proceeds.

Edge cases and pitfalls