L12. Iterative Postorder Traversal Using 1 Stack | C++ | Java | Binary Trees

Mastering tree traversals is a cornerstone of data structures and algorithms. While postorder traversal (Left -> Right -> Root) is naturally recursive, implementing it iteratively traditionally requires two stacks. This lecture breaks down an elegant, advanced optimization: performing an iterative postorder traversal using only a single stack.

1. Why Do We Need This? (Problem Statement & Status Quo)

• Postorder Traversal Definition: Visiting nodes in the specific order of Left -> Right -> Root.
• Recursive Approach Recap: In recursion, the call stack implicitly manages the execution state:
  Structure & Concept Flow

  Copy DiagramCopy

  go left -> go left -> go left -> reach null -> go right -> print/store root

   
• The Two-Stack Limitation: The standard iterative approach uses two stacks (stack1 for traversal and stack2 for reversing order to achieve Left-Right-Root).
• The Single-Stack Challenge: Optimizing space and control flow by dropping the second stack and maintaining all state transitions using a single stack and a temporary tracking pointer (temp).

2. Core Mental Model & Analogy

Real-Life Analogy: Navigating a maze with multiple dead ends. Imagine walking down the deepest left corridors first until you hit a dead end (null). Instead of getting lost, you drop breadcrumbs (pushing nodes onto the stack). When you can't go left anymore, you peek sideways to check if there is an unvisited right corridor. If you explore a right corridor or hit a dead end on both sides, you retrace your steps backward out of the maze, picking up your breadcrumbs in the exact sequence required to satisfy Left -> Right -> Root.

3. The Intuition: Going Deep Left First

To achieve postorder traversal iteratively with one stack, the algorithm mimics the recursive dive:

1. Push and Dive Left: Start at the root node (curr). Push the current node onto the stack, then traverse to its left child (curr = curr.left). Repeat this until curr becomes null.
2. Handle Right Subtrees & Backtracking: Once curr is null, we cannot go left anymore. We inspect the top of the stack to see if its right child exists and has been visited.
   • If a right child exists and we haven't processed it yet, we pivot to that right child.
   • If there is no right child (or the right subtree has already been processed), we pop the node from the stack, add it to our postorder result list, and set up a tracking mechanism to bubble back up to the parent.

4. Step-by-Step Dry Run Walkthrough

Let's trace how the algorithm processes a binary tree using a single stack and a temporary pointer (temp).

Initial Setup

• curr points to root 1.
• stack is empty.
• postorder list is empty.

Phase 1: Pushing Extreme Lefts

• Push 1, curr moves to 2 (left of 1).
• Push 2, curr moves to 3 (left of 2).
• Push 3, curr moves to null (left of 3).

Stack (Top to Bottom): [3, 2, 1]
curr: null

Phase 2: Processing Right Subtrees and Backtracking

• Since curr is null, we inspect the top of the stack (3).
• We check 3's right child (4). Since temp points to 4 (not null), we reassign curr = 4.
• From 4, we attempt to go left (null), come back, check 4's right child (5), and repeat the sinking and popping mechanism.

As nodes are popped when their right subtrees are fully explored, they are appended to the postorder list in the exact sequence of Left -> Right -> Root.

5. Complete Algorithm Implementation

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

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

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> postorder;
        if (root == NULL) return postorder;
        
        stack<TreeNode*> st;
        TreeNode* curr = root;
        
        while (curr != NULL || !st.empty()) {
            if (curr != NULL) {
                st.push(curr);
                curr = curr->left;
            } else {
                TreeNode* temp = st.top()->right;
                if (temp == NULL) {
                    temp = st.top();
                    st.pop();
                    postorder.push_back(temp->val);
                    
                    // Check if we came from a right child of the parent stack top
                    while (!st.empty() && temp == st.top()->right) {
                        temp = st.top();
                        st.pop();
                        postorder.push_back(temp->val);
                    }
                } else {
                    curr = temp;
                }
            }
        }
        return postorder;
    }
};

Java Implementation

import java.util.*;

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

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> postorder = new ArrayList<>();
        if (root == null) return postorder;
        
        Stack<TreeNode> st = new Stack<>();
        TreeNode curr = root;
        
        while (curr != null || !st.isEmpty()) {
            if (curr != null) {
                st.push(curr);
                curr = curr.left;
            } else {
                TreeNode temp = st.peek().right;
                if (temp == null) {
                    temp = st.pop();
                    postorder.add(temp.val);
                    
                    while (!st.isEmpty() && temp == st.peek().right) {
                        temp = st.pop();
                        postorder.add(temp.val);
                    }
                } else {
                    curr = temp;
                }
            }
        }
        return postorder;
    }
}

6. Complexity Analysis

7. Real-World Practical Pitfalls & Edge Cases

• Null Root Check: Always handle the edge case where the root is null immediately at the beginning to avoid null pointer exceptions.
• Infinite Loops via Incorrect Backtracking: Failing to correctly check temp == st.top()->right during upward bubbling can result in infinite loops or missing nodes. Ensure the nested while loop cleanly pops all ancestral nodes whose right subtrees have been fully evaluated.

Summary and Key Takeaways

• Postorder Sequence: Always follows the strict structural order of Left -> Right -> Root.
• Single-Stack Efficiency: Eliminates the overhead of a second auxiliary stack by utilizing a smart pointer (temp) to track right-child execution states.
• Extreme Left Dive: The traversal pattern aggressively pushes left nodes onto the stack until a null boundary is hit.
• Backtracking Mechanics: Uses stack top inspection (st.top()->right) to determine whether to explore a right child or pop and record the parent node.
• Linear Time Performance: Executes in $O(2N)$ time, visiting each node twice in the worst-case configuration.
• Auxiliary Space: Requires $O(N)$ stack space in the worst-case scenario for skewed binary trees.