Iterative Postorder Traversal of a Binary Tree

1. Introduction

Postorder traversal follows this visiting order:

Left → Right → Root

In the recursive version, the call stack takes care of visiting nodes in the correct order. But in iterative postorder traversal, we must manually simulate the stack behavior.

2. Why Postorder Is Tricky Iteratively

Unlike preorder (Root → Left → Right) and inorder (Left → Root → Right) traversals, postorder requires that the root node be processed after its children.

This makes it non-trivial to implement iteratively because:

You need to delay processing the root until both left and right children are done.
Simply using one stack like in inorder traversal won’t work without tricks.

3. Approaches to Iterative Postorder Traversal

There are two common approaches:

Approach 1: Using Two Stacks (Easy and intuitive)

First stack simulates the postorder traversal.
Second stack stores the reverse of the postorder output (Root → Right → Left).
Finally, pop the second stack to get Left → Right → Root.

Approach 2: Using One Stack and a Last Visited Pointer (More space-efficient)

Uses a single stack and keeps track of the last node visited.
Ensures that a node is processed only after both children have been processed.

4. Tree Example for This Tutorial

We’ll use the following tree:

Postorder Output:

4 5 2 3 1

5. Iterative Postorder Using Two Stacks

Step-by-Step Algorithm

Push the root node into stack1.
Pop from stack1 and push it to stack2.
Push left and then right child of popped node into stack1.
Repeat until stack1 is empty.
Pop all elements from stack2 → this is your postorder traversal.

import java.util.*;

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

public class PostorderIterativeTwoStacks {

    public void postorderTraversal(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();

        stack1.push(root);

        while (!stack1.isEmpty()) {
            TreeNode curr = stack1.pop();
            stack2.push(curr);

            // Note: Push left before right so right is processed first
            if (curr.left != null) stack1.push(curr.left);
            if (curr.right != null) stack1.push(curr.right);
        }

        // Print postorder from stack2
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }

    public static void main(String[] args) {
        /*
              1
             / \
            2   3
           / \
          4   5
        */

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        PostorderIterativeTwoStacks tree = new PostorderIterativeTwoStacks();
        System.out.println("Iterative Postorder Traversal:");
        tree.postorderTraversal(root);  // Output: 4 5 2 3 1
    }
}

6. Visual Walkthrough: Two Stack Approach

Initial Tree:

Stack States:

stack1: [1]
stack2: []

Pop 1 → Push to stack2 → stack2: [1]
Push 2 and 3 → stack1: [2, 3]

Pop 3 → Push to stack2 → stack2: [1, 3]
Pop 2 → Push to stack2 → stack2: [1, 3, 2]
Push 4 and 5 → stack1: [4, 5]

Pop 5 → Push to stack2 → stack2: [1, 3, 2, 5]
Pop 4 → Push to stack2 → stack2: [1, 3, 2, 5, 4]

Final postorder = pop all from stack2 → 4 5 2 3 1

7. Iterative Postorder Using One Stack and Last Visited Pointer

Algorithm

Traverse left subtree, pushing nodes to the stack.
When at the top of the stack, peek (don’t pop yet).
If the right child is null or already visited, visit and pop the node.
Otherwise, go to the right child.

public class PostorderIterativeOneStack {

    public void postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode lastVisited = null;
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // Step 1: Traverse to leftmost node
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                TreeNode peekNode = stack.peek();

                // Step 2: If right child exists and wasn’t visited, go right
                if (peekNode.right != null && lastVisited != peekNode.right) {
                    current = peekNode.right;
                } else {
                    // Step 3: Visit node
                    System.out.print(peekNode.val + " ");
                    lastVisited = stack.pop();
                }
            }
        }
    }

    public static void main(String[] args) {
        /*
              1
             / \
            2   3
           / \
          4   5
        */

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        PostorderIterativeOneStack tree = new PostorderIterativeOneStack();
        System.out.println("Postorder Traversal (One Stack):");
        tree.postorderTraversal(root);  // Output: 4 5 2 3 1
    }
}

8. Time and Space Complexity

Metric	Two Stack Approach	One Stack Approach
Time Complexity	O(n)	O(n)
Space Complexity	O(n) (2 stacks)	O(n) (1 stack)
Traverses Each Node	Once	Once