Iterative Postorder Traversal using Two Stacks (Binary Tree)

Postorder tree traversal visits nodes in the specific order of Left -> Right -> Root. While recursive postorder traversal is straightforward, implementing it iteratively requires careful management of node exploration order. This chapter explores how to achieve iterative postorder traversal efficiently using two auxiliary stacks, complete with step-by-step dry runs, complexity analysis, and production-ready implementations in C++ and Java.

1. Why Do We Need Iterative Postorder Traversal?

Recursive traversal relies implicitly on the system call stack. When dealing with extremely deep binary trees in production environments, recursion can lead to a dreaded StackOverflowError due to memory limits on the call stack.

Converting recursive algorithms into iterative solutions using explicit data structures (stack) gives developers precise control over memory management, prevents recursion overhead, and avoids stack overflow crashes in deep tree structures.

2. Core Mental Model and Traversal Definition

Postorder traversal follows a strict rule for every subtree:

1. Left Subtree: Fully explore the left child and its descendants.
2. Right Subtree: Fully explore the right child and its descendants.
3. Root Node: Process or visit the parent/root node last.

Sample Binary Tree for Our Walkthrough

Consider the following binary tree structure:

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

For this tree, the expected postorder traversal sequence is: [4, 5, 2, 8, 7, 6, 3, 1].

3. The Two-Stack Strategy: Intuition & Concept

To simulate the postorder sequence iteratively without recursion, we can leverage two stacks (stack1 and stack2):

• stack1: Used to process nodes in a modified Preorder-like fashion (Root -> Right -> Left) so that when we pop items off, we can push them into stack2.
• stack2: Acts as a holding container that reverses the order naturally, ensuring that when we finally pop everything out of stack2, we get the exact Left -> Right -> Root postorder sequence.

4. Step-by-Step Algorithm Walkthrough

1. Initialization:
   • Check if the root is null. If so, return an empty list.
   • Create stack1 and stack2.
   • Push the root node into stack1.
2. Processing Loop: While stack1 is not empty:
   • Pop the top node from stack1 (let's call it current).
   • Push current into stack2.
   • If current has a left child, push the left child into stack1.
   • If current has a right child, push the right child into stack1.
3. Final Collection: Once stack1 is completely empty, all nodes have been transferred to stack2 in the correct reversed sequence. Pop all elements from stack2 sequentially to form the final postorder traversal list.

5. Complete Flow Trace

Let's trace the algorithm step-by-step using our sample tree rooted at 1.

Initial State:
stack1 = [1]
stack2 = []

When stack1 is empty, we pop everything from stack2 from top to bottom, yielding: [4, 5, 2, 8, 7, 6, 3, 1] (Postorder traversal).

6. Implementation Code (C++ and Java)

C++ Implementation

#include <iostream>
#include <vector>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> postorderResult;
        if (root == nullptr) {
            return postorderResult;
        }

        std::stack<TreeNode*> stack1;
        std::stack<TreeNode*> stack2;

        stack1.push(root);

        while (!stack1.empty()) {
            TreeNode* current = stack1.top();
            stack1.pop();
            stack2.push(current);

            // Push left child first so that right is processed first in stack1
            if (current->left != nullptr) {
                stack1.push(current->left);
            }
            if (current->right != nullptr) {
                stack1.push(current->right);
            }
        }

        // Transfer all elements from stack2 to result vector
        while (!stack2.empty()) {
            postorderResult.push_back(stack2.top()->val);
            stack2.pop();
        }

        return postorderResult;
    }
};

Java Implementation

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> postorderResult = new ArrayList<>();
        if (root == null) {
            return postorderResult;
        }

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

        stack1.push(root);

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

            // Push left child first, then right child
            if (current.left != null) {
                stack1.push(current.left);
            }
            if (current.right != null) {
                stack1.push(current.right);
            }
        }

        // Pop from stack2 to get Left -> Right -> Root order
        while (!stack2.isEmpty()) {
            postorderResult.add(stack2.pop().val);
        }

        return postorderResult;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Definition: Postorder traversal visits nodes in Left -> Right -> Root order.
• Two-Stack Approach: Utilizes stack1 for node traversal exploration and stack2 for reversing the sequence into correct postorder format.
• Push Order Matters: In stack1, push the left child first and the right child second, ensuring the right child is processed before the left child during pops.
• Robustness: Eliminates recursion overhead, preventing StackOverflowError on deeply skewed trees.
• Next Steps: While the two-stack solution is intuitive and clean, postorder traversal can also be optimized to use a single stack, which will be explored in the subsequent chapter.