☕ DSA Java Articles

Topics › Binary Trees › Traversals

Post-order Traversal of Binary Tree using 1 stack

Easy TUF ID 2787 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return the values of its nodes in postorder: the whole left subtree, then the whole right subtree, then the node itself. The point of this exercise is to do it iteratively with a single explicit stack: no recursion and no second stack. An empty tree gives an empty list.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in an int. Values may repeat, so nodes must be told apart by identity, not by value.

Example 1

tree (level order) = [1, 2, 3, 4, 5, 6, 7]

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

answer = [4, 5, 2, 6, 7, 3, 1]   // both children always come before their parent

Example 2

tree (level order) = [1, null, 2, 3]

   1
    \
     2
    /
   3

answer = [3, 2, 1]               // 1 has no left subtree, so its right subtree comes first

Why is postorder the awkward one? A depth-first walk reaches every node three times: on the way down, when it comes back from the left child, and when it comes back from the right child. Preorder prints at the first visit and inorder at the second, and both are easy with a stack. Postorder prints at the third visit. A stack remembers the path back to the root, but by itself it cannot tell whether we are returning from the left side or from the right side. Every iterative postorder method is a way of answering that one question.

Approach 1: Recursion

Intuition. The definition is recursive, so the code is too: postorder of a tree is postorder of the left subtree, then postorder of the right subtree, then the root. The call stack silently remembers which child we came back from, because each call returns to the exact line after the one that made it.

Algorithm.

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

static void postorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    postorder(node.left, out);
    postorder(node.right, out);
    out.add(node.val);
}

Complexity. Time O(n): every node is entered once. Space O(h) for the call stack, where h is the height of the tree. On a skewed tree of 10^5 nodes, h = 10^5 and the JVM’s default thread stack may overflow, which is the practical reason to learn the iterative versions.

Approach 2: Two stacks

Intuition. Read postorder backwards: root, right, left. That is just a preorder in which the right child is visited before the left one, and preorder is easy with a stack because a node is finished the moment it is popped. So produce root-right-left with one stack and push every popped node onto a second stack. Popping the second stack then reverses the sequence into left-right-root.

Algorithm.

  1. Push the root onto st1.
  2. While st1 is not empty: pop a node, push it onto st2, then push its left child and then its right child onto st1 (the right one is on top, so it is processed first).
  3. Pop everything from st2 into the answer.
static List<Integer> twoStacks(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> st1 = new ArrayDeque<>(), st2 = new ArrayDeque<>();
    st1.push(root);
    while (!st1.isEmpty()) {
        TreeNode node = st1.pop();
        st2.push(node);
        if (node.left != null) st1.push(node.left);
        if (node.right != null) st1.push(node.right);
    }
    while (!st2.isEmpty()) out.add(st2.pop().val);
    return out;
}

Complexity. Time O(n): each node is pushed and popped once on each stack. Space O(n): st2 ends up holding every node, whatever the shape of the tree. It also cannot emit anything until the whole tree has been read. That full extra copy of the tree is what the one-stack method gets rid of.

Approach 3: One stack

Intuition. Simulate the recursion directly. The stack holds the path from the root to where we are, that is, the nodes whose postorder moment has not arrived yet. We go left as far as we can, pushing every node on the way. When we fall off the bottom (cur == null), we look at the top node:

The clever part is what happens right after a pop. Say we popped node X. If X is the right child of the new top, then the new top’s right subtree has just been completed, and its left subtree was completed earlier, so the new top is finished too: pop and output it, and repeat the same test with the next node down the stack. If X was a left child, we stop, and the next round explores the parent’s right subtree. The comparison temp == st.peek().right is exactly the “which side did I come back from?” question from the problem statement.

Algorithm.

  1. cur = root. Loop while cur != null or the stack is not empty.
  2. If cur != null: push it and move cur = cur.left.
  3. Otherwise let temp = top.right.
    • If temp != null: set cur = temp and continue.
    • If temp == null: pop the top into temp and output it. Then, while the stack is not empty and temp is the right child of the top, pop the top into temp and output it.
static List<Integer> oneStack(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !st.isEmpty()) {
        if (cur != null) {
            st.push(cur);
            cur = cur.left;
        } else {
            TreeNode temp = st.peek().right;
            if (temp == null) {
                temp = st.pop();
                out.add(temp.val);
                while (!st.isEmpty() && temp == st.peek().right) {
                    temp = st.pop();
                    out.add(temp.val);
                }
            } else {
                cur = temp;
            }
        }
    }
    return out;
}

Dry run on Example 1 (stack written bottom to top):

step event stack after output so far
1 push 1, 2, 4 going left 1 2 4  
2 top 4 has no right: pop 4; 4 is not 2’s right child, stop 1 2 4
3 top 2 has right child 5: cur = 5, push 5 1 2 5 4
4 top 5 has no right: pop 5; 5 is 2’s right child: pop 2; 2 is not 1’s right child, stop 1 4 5 2
5 top 1 has right child 3: push 3, then 6 going left 1 3 6 4 5 2
6 pop 6; 6 is not 3’s right child, stop 1 3 4 5 2 6
7 top 3 has right child 7: push 7 1 3 7 4 5 2 6
8 pop 7; 7 is 3’s right: pop 3; 3 is 1’s right: pop 1 empty 4 5 2 6 7 3 1

The loop ends because cur is null and the stack is empty.

Complexity. Time O(n): every node is pushed exactly once and popped exactly once; the inner while only pops nodes, so across the whole run it does at most n iterations in total. Space O(h): the stack only ever holds one root-to-node path.

A variant with a lastVisited pointer. Many people find this form easier to remember. Instead of popping a chain, remember the last node that was output. The top is finished when its right child is null or is exactly the node we output last (we only output a right child after its whole subtree, so that means the right side is done). Otherwise we still have to go right.

static List<Integer> oneStackLastVisited(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    TreeNode cur = root, lastVisited = null;
    while (cur != null || !st.isEmpty()) {
        if (cur != null) {
            st.push(cur);
            cur = cur.left;
        } else {
            TreeNode top = st.peek();
            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 finished
                lastVisited = st.pop();
            }
        }
    }
    return out;
}

Both one-stack versions do the same pushes and pops; they only differ in how they detect a finished right subtree. The Java file runs them, and the two-stack version, on 300 seeded random trees against the recursive answer.

Edge cases and pitfalls