☕ DSA Java Articles

Topics › Binary Trees › Traversals

Post-order Traversal of Binary Tree using 2 stack

Easy TUF ID 2788 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its postorder traversal (left subtree, right subtree, then the node) without recursion, using two stacks. An empty tree gives an empty list.

Constraints: between 0 and 10^5 nodes, arbitrary 32-bit values, duplicates allowed. The tree can be a single chain of 10^5 nodes, which is deep enough to break a recursive solution on a default Java stack.

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

Example 1

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
root = [1, 2, 3, 4, 5, 6, 7]
answer = [4, 5, 2, 6, 7, 3, 1]   // each node after both of its subtrees; the root comes last

Example 2

    1
     \
      2
     /
    3
root = [1, null, 2, 3]
answer = [3, 2, 1]

Why is postorder the awkward one to do iteratively? In preorder a node is emitted as soon as it is reached; in inorder it is emitted after its left subtree. In postorder it must wait until both subtrees are finished, so a single pass from the top cannot emit anything until it reaches the bottom. The two-stack method sidesteps the problem by generating the answer backwards.

Approach 1: Recursion (the reference)

Intuition. Postorder is defined recursively, so the recursive code is direct: left subtree, right subtree, node. It is the answer every iterative method must match, and it is what the Java tests compare against.

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;
    postorder(node.left, out);                // Left
    postorder(node.right, out);               // Right
    out.add(node.val);                        // Root
}

Complexity. Time O(n), space O(h) for the call stack, which is O(n) on a skewed tree. That is the limitation the rest of the article removes.

Approach 2: Two stacks

Intuition. Read postorder backwards. The reverse of Left, Right, Root is Root, Right, Left, which is a preorder walk that simply visits the right child before the left one. Preorder-style walks are easy with a stack: pop a node, handle it, push its children. So:

Why it is exactly postorder. By induction on the tree: stack 1 emits the root, then the whole right subtree in Root-Right-Left order, then the whole left subtree in Root-Right-Left order. Reversing a concatenation A B C gives reverse(C) reverse(B) reverse(A). Applying the induction hypothesis to the subtrees, that is 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 onto stack 1.
  3. While stack 1 is not empty: pop a node, push it onto stack 2, then push its left child and then its right child onto stack 1 (each only if present).
  4. Pop every node from stack 2 into the output.
static List<Integer> twoStacks(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode node = s1.pop();
        s2.push(node);                                    // s2 receives Root, Right, Left (bottom to top)
        if (node.left != null) s1.push(node.left);        // left pushed first ...
        if (node.right != null) s1.push(node.right);      // ... so right is popped first
    }
    while (!s2.isEmpty()) out.add(s2.pop().val);          // popping s2 reverses it: Left, Right, Root
    return out;
}

Dry run on Example 1. Stacks are written bottom to top, so the right end is the top.

Step Popped from s1 s1 after pushing children s2
1 1 [2, 3] [1]
2 3 [2, 6, 7] [1, 3]
3 7 [2, 6] [1, 3, 7]
4 6 [2] [1, 3, 7, 6]
5 2 [4, 5] [1, 3, 7, 6, 2]
6 5 [4] [1, 3, 7, 6, 2, 5]
7 4 [] [1, 3, 7, 6, 2, 5, 4]

Popping s2 from the top gives 4, 5, 2, 6, 7, 3, 1, the expected answer.

Complexity. Time O(n): every node is pushed and popped once on each stack. Space O(n): stack 2 eventually holds every node. Stack 1 itself stays small, O(h), since it only holds pending left children along the current path.

Approach 3: One stack, prepend to the output

Intuition. Stack 2 is only a reversing device. We get the same effect by prepending each popped value to the front of the output list: the first value generated ends up last. A LinkedList supports addFirst in constant time, so the second stack disappears while the logic stays identical.

Do not do this with ArrayList.add(0, x): inserting at the front of an array list shifts every existing element, which makes the method O(n^2).

Algorithm.

  1. If the root is null, return an empty list.
  2. Push the root. While the stack is not empty: pop a node, addFirst its value, push its left child and then its right child.
static List<Integer> oneStackPrepend(TreeNode root) {
    LinkedList<Integer> out = new LinkedList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.addFirst(node.val);                           // prepending reverses the order as it is built
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return out;
}

Complexity. Time O(n). Space O(h) for the stack besides the output list itself. Like Approach 2, nothing is final until the end: the first value of the answer is the last one inserted. If you need to produce values in order as you go, or stop early, the single-stack method with a last-visited pointer is the right tool.

Edge cases and pitfalls