Iterative Postorder Traversal: The Two Methods Worth Knowing

Preorder was a one-line swap in push order. Inorder settled into a clean left-spine rhythm. Iterative postorder traversal fights back. You hit a node, push it onto the stack, descend into its children, and then you still cannot process it. You have to finish the entire left subtree and the entire right subtree before the node gets its turn. That constraint is invisible in recursion. The call stack handles it automatically while your three-line implementation looks very clever. Going iterative means simulating that bookkeeping yourself.

The core difficulty: you cannot process a node when you first encounter it. In preorder and inorder, every pop is a visit. In postorder, a pop might just mean "I'm back at this node." You only visit it once both children are done.

This is Part 3 of a three-part series on iterative binary tree traversal. Here you get both solutions: a two-stack approach that is easy to implement but costs O(n) auxiliary space, and a single-stack approach with a lastVisited pointer that brings it back to O(h). Neither is obvious the first time you see it.

Welcome to the appropriate context.

Why Recursion Gets This for Free

The recursive postorder is three lines:

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)   # always last

The call stack does all the bookkeeping. Each frame suspends, waits for both recursive calls to finish, and then runs visit. That "suspend and wait" is the thing you have to simulate by hand. Also, Python's default recursion limit is 1000. LeetCode test cases routinely hit 10^4 nodes. You can call sys.setrecursionlimit(200000) and hope for the best, or write it iteratively. One of these impresses your interviewer.

The question you have to answer at every node: "Have I already processed the right subtree?" If yes, pop and visit. If no, go right first and come back.

What Each Method Is Actually Doing

Both methods maintain an explicit stack that mirrors the call stack. The difference is in how they answer the "is the right subtree done?" question.

Two stacks sidestep the question entirely by inverting the problem. One stack threads a single lastVisited pointer through the iteration to answer it directly.

Here is the example tree used throughout:

Orange badge = visit order. Postorder always processes children before parent.

      1
     / \
    2   3
   / \
  4   5

Postorder answer: [4, 5, 2, 3, 1].

The Two-Stack Method

This is the best party trick in tree traversal. Show your interviewer the approach before explaining how it works. Watch their face. Then explain.

Postorder (left, right, root) reversed is (root, right, left), which is just preorder with left and right swapped. So the plan: run a "modified preorder" that produces root, right, left order, collect every node's value in a second stack as you go, then reverse. The second stack's pop order is the postorder sequence.

Algorithm:

1. Push root onto stack1.
2. Pop a node from stack1. Push its value onto stack2. Push its left child (if any), then its right child (if any) onto stack1. Right is pushed last so it pops first, giving root-right-left order.
3. Repeat until stack1 is empty.
4. Pop everything from stack2. That is the postorder traversal.

def postorder_two_stacks(root):
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node.val)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    return stack2[::-1]

Step-by-step trace on the example tree:

Stack2 collects root-right-left. Reverse it. That's postorder.

Why it works

The values in stack2 arrive in root-right-left order because:

• The root of any subtree is always popped first from stack1 (it was pushed first or via parent).
• Right child is always on top of stack1 (pushed after left), so right subtrees are processed before left subtrees.

Reverse root-right-left and you get left-right-root, which is postorder.

The space cost

stack1 holds at most O(h) nodes at any moment (same argument as iterative preorder: at each depth level, at most one pending sibling is waiting on the stack). stack2 accumulates all n values before you read any of them. Total auxiliary space is O(n).

Fine for most interview problems. Wrong shape if you need a tree iterator, a streaming computation, or a tree with 50 million nodes where buffering all values upfront actually matters.

The Single-Stack Method: O(h) Space

The single-stack approach adds one variable: lastVisited. lastVisited answers the question "did I just finish the right subtree?" in O(1).

Here is why that works. In postorder, the right child of a node is always the last thing visited before the node itself. So: if you are peeking at a node on the stack and lastVisited is that node's right child, the entire right subtree has been processed. You can safely pop and visit.

def postorder_one_stack(root):
    result = []
    stack = []
    current = root
    last_visited = None

    while current or stack:
        if current:
            stack.append(current)
            current = current.left
        else:
            peek = stack[-1]
            if peek.right and last_visited is not peek.right:
                current = peek.right
            else:
                stack.pop()
                result.append(peek.val)
                last_visited = peek

    return result

Step 8: peek is node 2, its right child is node 5, lastVisited is node 5. Same object. Right subtree is done. Pop and visit 2.

The left-spine descent (the if current: branch) is identical to inorder traversal. The new logic lives entirely in the else branch: before popping, check whether the right subtree still needs to be visited.

Step-by-step trace

Result: [4, 5, 2, 3, 1] ✓

Why lastVisited is peek.right is the right check

The right child of any node is the last node visited within that node's right subtree. Postorder within the right subtree visits: left of right child, right of right child, right child. The root of any subtree is always its own last node in postorder. So the moment peek.right gets visited, its entire subtree is done, and lastVisited will equal peek.right.

This also handles the no-right-child case cleanly: the condition short-circuits, and we pop immediately.

Correctness argument

Claim: when we pop a node, both subtrees are fully processed.

Left subtree: we always exhaust the left spine before checking the stack. By the time we peek at a node, its entire left subtree has been visited.

Right subtree: the lastVisited is not peek.right guard ensures we only pop when either there is no right child or lastVisited equals the right child (meaning the right subtree is done).

By induction on tree height, the invariant holds for every node in the tree.

Space: why the stack stays at O(h)

At any moment, the stack contains a single path from the root to some node: the ancestors of whatever node we are currently at or have just visited. We never have two sibling nodes simultaneously on the stack. When we go right (setting current = peek.right), the parent (peek) stays on the stack above, and the right child gets pushed on the next iteration. The stack remains a path. Maximum depth is h. So auxiliary space is O(h).

Complexity at a Glance

Time is O(n) for both: every node is pushed and popped exactly once.

O(h) is O(log n) for balanced trees and O(n) for degenerate (skewed) trees. In the worst case, both hit O(n). In practice, the single-stack version wins because real trees are not maximally skewed.

The iterator-friendly property is a real differentiator. If you need next() and hasNext() for postorder (the same pattern as the BST Iterator problem, applied to postorder instead of inorder), the single-stack method can be split at the pop. The two-stack method cannot yield anything until all n values are accumulated in stack2.

What Problems Call for Postorder Thinking

Postorder means bottom-up: a node's answer depends on its children's answers. Any problem where you aggregate information from subtrees before returning to the parent is postorder under the hood.

Concrete signals:

• You need the height, size, or sum of both subtrees before processing the current node.
• You are checking a property of the whole subtree (balanced, valid BST, symmetric).
• You are computing a value that "bubbles up" from leaves (diameter, LCA, subtree maximum).
• You are deleting or modifying nodes and need child state before acting on the parent.

The relationship to dynamic programming is direct. Bottom-up DP on trees is postorder traversal with memoization at each node. If you have used the dynamic programming framework to solve tree problems, you have been doing postorder traversal the whole time.

How to Spot a Postorder Problem

Signal: work happens after both recursive calls, not before.

Worked example 1: Diameter of a Binary Tree (LeetCode 543)

Problem: find the length of the longest path between any two nodes.

Why postorder: the diameter at any node is depth(left subtree) + depth(right subtree). You need both subtree depths before you can compute the current node's contribution. Compute depth on the way up, update a running maximum at each node.

def diameter_of_binary_tree(root):
    max_diameter = [0]

    def depth(node):
        if not node:
            return 0
        left = depth(node.left)    # postorder: children first
        right = depth(node.right)
        max_diameter[0] = max(max_diameter[0], left + right)
        return max(left, right) + 1

    depth(root)
    return max_diameter[0]

Every line of depth that runs after the recursive calls is postorder logic.

Worked example 2: Validate a BST by subtree range (LeetCode 98)

Problem: confirm that every node is within the valid range for its position in the BST.

This one looks preorder (pass bounds downward), but a node cannot report "my subtree is valid" until both children have reported back. Reporting correctness up to the parent is postorder. In an iterative implementation you carry (node, min_bound, max_bound) tuples on the stack and pop-and-validate only after both children are processed.

Worked example 3: Delete Nodes and Return Forest (LeetCode 1110)

Problem: given a set of values to delete, remove those nodes and return the roots of the resulting forest.

Why postorder: whether a node becomes a new root depends on whether its parent was deleted. Whether its children become new roots depends on whether the current node is deleted. You cannot make that decision for a node until you know what happened to its children. Process children first. Postorder.

One Structure, Every Language

All implementations below use the single-stack method for O(h) auxiliary space. The two-stack version is shorter but buffers all n values before returning, which makes it unsuitable for iterators or large trees.

One note that applies to every implementation: use identity comparison (pointer/reference equality), not value equality, when checking lastVisited. Two different nodes can have the same integer value and be completely different objects. Value equality returns True. The algorithm then visits the wrong node. The output looks correct until your test input has duplicate values. You will make this mistake once.

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None, right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right

def postorder_traversal(root: Optional[TreeNode]) -> list[int]:
    result: list[int] = []
    stack: list[TreeNode] = []
    current: TreeNode | None = root
    last_visited: TreeNode | None = None

    while current or stack:
        if current:
            stack.append(current)
            current = current.left
        else:
            peek = stack[-1]
            if peek.right and last_visited is not peek.right:
                current = peek.right
            else:
                stack.pop()
                result.append(peek.val)
                last_visited = peek

    return result

Which Iterative Postorder Method to Reach For

Use two stacks when:

• You are solving a LeetCode problem and want a clean, quickly-debugged solution.
• The problem does not ask for an iterator or streaming output.
• The tree is guaranteed to be small enough that O(n) extra memory is fine.

Use single-stack when:

• You need an iterator (next() / hasNext() for postorder).
• The tree could be deep and skewed, making O(n) auxiliary memory a real concern.
• You are implementing a tree-based computation engine or evaluator where results stream out one at a time.

In interviews, naming both approaches and explaining the tradeoff is often worth more than just producing one working solution.

What to Take Away

• Postorder is harder iteratively because you cannot visit a node when you first see it.
• Two-stack: invert the problem. Collect root-right-left order in a second stack, then reverse. O(n) auxiliary space. Simple to implement.
• Single-stack: use a lastVisited pointer to answer "is the right subtree done?" in O(1). O(h) auxiliary space. Iterator-friendly.
• lastVisited == peek.right holds because in postorder, the right child is always the last node visited within the right subtree.
• Always use identity comparison (pointer equality), not value equality, when checking lastVisited.
• The postorder pattern is bottom-up aggregation: children before parent. Diameter, height, balance check, LCA, subtree sums, node deletion.
• Bottom-up DP on a tree is postorder traversal. The shapes are the same.

Reading about which traversal to use and deciding in 60 seconds during a real interview are different skills. SpaceComplexity runs real-time voice mock interviews with rubric-based feedback on exactly this kind of pattern recognition. Worth a try when articles stop feeling like prep.

Further Reading

• Binary Tree Postorder Traversal (LeetCode 145)
• Tree Traversal (Wikipedia)
• Iterative Postorder Traversal (GeeksforGeeks)
• std::stack (cppreference)
• ArrayDeque (Java SE 21 docs)
• Diameter of Binary Tree (LeetCode 543)