Binary Tree Post-Order Traversal, in depth: the last-visited stack, bottom-up folds and where children-first matters

The rule and its two structural facts

Every depth-first traversal of a binary tree passes each node three times: on the way down, between the two subtrees, and on the way back up. Pre-order emits the node on the first pass, in-order on the second, post-order on the third. The recursive version is three lines.

def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)      # the node is emitted after both subtrees are complete

Two structural facts follow. First, the root is always the last element of the output, and the root of every subtree is the last element of that subtree's block. Second, every subtree occupies a contiguous block of the output, left subtree block, then right subtree block, then the root. Those facts are what let you rebuild a tree from its in-order and post-order sequences, and what make post-order the natural shape for any computation that folds a tree into a value.

Running time is O(n): each node is entered once and emitted once. Extra space is O(h) for the call stack, where h is the height. For a balanced tree that is O(log n); for a degenerate tree, where every node has only one child, it is O(n), and that case is the reason iterative versions exist.

The example tree

The tree above holds the keys 8, 3, 10, 1, 6, 14, 4, 7 and 13. Its post-order is 1 4 7 6 3 13 14 10 8. Read the left subtree of 8 as the block 1 4 7 6 3, which ends with its root 3, and the right subtree as 13 14 10, which ends with 10. Inside the left block, the subtree rooted at 6 is 4 7 6. The nesting repeats at every level, which is a quick way to check any post-order sequence by eye.

The single-stack iterative algorithm

Converting post-order to a loop is harder than converting pre-order. In pre-order you can emit a node the moment you pop it. In post-order a node on top of the stack may be there for two different reasons: you have just finished its left subtree and still need to go right, or you have finished both subtrees and it is time to emit it. The single-stack algorithm tells those cases apart by remembering the last node it emitted.

def postorder_iterative(root):
    out, stack = [], []
    node, last = root, None
    while stack or node is not None:
        if node is not None:            # walk as far left as possible
            stack.append(node)
            node = node.left
            continue
        top = stack[-1]
        if top.right is not None and last is not top.right:
            node = top.right            # right subtree not done yet: go there
        else:
            out.append(top.val)         # both subtrees done: emit
            last = stack.pop()
    return out

The key comparison is last is not top.right. If the node we just emitted is the right child of the node on top of the stack, the right subtree is complete, because post-order emits a subtree's root last. If there is no right child, the left subtree being done is enough. The comparison must use identity, not value: a tree with duplicate keys would otherwise make the algorithm think a subtree is finished when it is not.

The stack never holds more than h plus one nodes, the same bound as recursion, but it lives on the heap where it can grow to millions of entries without overflowing the thread's call stack.

Tracing the stack

Here is the stack at each emit on the example tree. The stack is listed bottom to top after the pop.

The deepest the stack gets is four nodes, for example 8 3 6 4 just before 4 is emitted. That is the height of the tree in edges, three, plus one. Step 7 is worth studying: 14 has a left child but no right child, so once 13 is emitted the check falls straight to the emit branch.

Bottom-up computation in one pass

The real value of post-order is that each node can combine results from its children. Write the traversal to return a tuple and you can compute several properties in one pass. The following computes height, diameter (the longest path between any two nodes, in edges), subtree size and whether the tree is height-balanced.

def summarize(node):
    """Return (height, diameter, size, balanced) for the subtree at node.
    Height of an empty tree is -1, so a leaf has height 0."""
    if node is None:
        return -1, 0, 0, True
    lh, ld, ls, lb = summarize(node.left)
    rh, rd, rs, rb = summarize(node.right)
    height   = 1 + max(lh, rh)
    through  = lh + rh + 2                  # longest path that bends at this node
    diameter = max(ld, rd, through)
    size     = 1 + ls + rs
    balanced = lb and rb and abs(lh - rh) <= 1
    return height, diameter, size, balanced

On the example tree, the leaves 1, 4, 7 and 13 return height 0. Node 6 returns height 1. Node 3 sees heights 0 and 1 and returns height 2. On the right, 14 has height 1 and 10 has height 2 with a missing left child of height minus one, so 10 is unbalanced: the difference is 2. The root returns height 3, size 9, balanced false, and diameter 6, the path 4, 6, 3, 8, 10, 14, 13, which bends at the root with 2 plus 2 plus 2 edges.

Compare that with the naive approach of calling a separate height function at every node, which costs O(n log n) on balanced trees and O(n squared) on degenerate ones. The post-order version is O(n) because each subtree's height is computed exactly once and reused by its parent.

To compute the same thing without recursion, keep the single-stack loop and store results in a dictionary keyed by node identity. At the emit step, read the results of the two children, which are guaranteed to be present, combine them, store the node's own result and delete the children's entries. Memory stays proportional to the stack plus a frontier of finished subtrees.

def heights_iterative(root):
    """Height of every subtree without recursion; returns the root's height."""
    done = {}                                  # id(node) -> height of finished subtree
    stack, node, last = [], root, None
    while stack or node is not None:
        if node is not None:
            stack.append(node)
            node = node.left
            continue
        top = stack[-1]
        if top.right is not None and last is not top.right:
            node = top.right
            continue
        lh = done.pop(id(top.left), -1)        # children finished earlier, so present
        rh = done.pop(id(top.right), -1)
        done[id(top)] = 1 + max(lh, rh)
        last = stack.pop()
    return done.get(id(root), -1)

The loop is the same as before; only the emit step changed. Popping the children's entries as they are consumed keeps the dictionary small: at any moment it holds results only for finished subtrees whose parent has not yet been emitted, which is at most one or two per level of the stack. The same skeleton computes sums, sizes, minimums or any other value that combines children, so it is worth keeping as a template rather than rewriting the control flow each time.

Where children-first matters in real systems

The same children-first shape appears throughout systems code.

• Expression evaluation. The post-order of an expression tree is its reverse Polish notation. The tree for (3 + 4) * (5 - 2) produces 3 4 + 5 2 - *, which a stack machine evaluates to 21: push operands, and at each operator pop two values and push the result. Compilers generate stack-machine bytecode this way.
• Freeing memory. A node can be destroyed only after its children, or you read a freed pointer to find them. Recursive destructors on deep trees, such as a long linked chain of owning pointers, can overflow the call stack; production code tears such structures down iteratively.
• Directory sizes. The disk usage of a directory is its own files plus the totals of its subdirectories, so a usage tool must finish the children first.
• Build systems. Building every dependency before its dependents is post-order on the dependency graph; reversing a depth-first finish order gives a topological order of a directed acyclic graph.

Alternatives and what they cost

Reversed pre-order is the trick most interview answers use, and it is correct, but notice what it gives up. It cannot emit anything until the whole tree is seen, so it cannot drive a computation that combines child results as it goes, and it needs memory proportional to n, not to h. For a bottom-up fold, use the last-pointer version.

Failure modes

• Missing the last-visited check. Without it, the loop returns to the right subtree forever after finishing it. Symptom: an infinite loop on any node with a right child.
• Comparing by value. last.val == top.right.val breaks on trees with duplicate keys.
• Updating last on the wrong branch. Setting last when moving right instead of when emitting makes the right child look finished before it has been visited.
• Mutating during traversal. Deleting a child before the parent's emit step reads it, which in C or C++ is a use-after-free.
• Recursion on unbounded input. A parser that builds a left-deep tree from a long chain such as a + a + a + ... crashes the recursive evaluator. Bound the depth or iterate.

Testing, and where to go from here

Test with the empty tree, a single node, a left-only chain, a right-only chain, a complete tree, and a tree with duplicate keys. Compare the iterative output with the recursive output on thousands of random trees; random differential testing catches the last-pointer bugs above within seconds. Add one degenerate tree of a million nodes to prove the iterative version does not overflow.

To keep learning, compare with pre-order traversal and in-order traversal, see the general method for converting recursive DFS to an explicit stack, apply the bottom-up pattern in tree diameter, and use post-order with in-order in rebuilding a tree from traversals.

What to do next

1. Write the recursive version and the single-stack version, and check they agree on the example tree.
2. Run a differential test against random trees, including duplicates and degenerate chains.
3. Rewrite one of your height or size helpers as a single post-order pass returning a tuple.
4. Evaluate a reverse Polish expression with a stack, then build its expression tree and confirm the post-order matches.
5. Find any recursive teardown or evaluator in your codebase that runs on user-controlled depth and bound or iterate it.