Binary Tree Postorder Traversal

Binary Tree Postorder Traversal asks for the node values in postorder: every node comes after both of its subtrees. It is a classic warm-up for the iterative tree-traversal pattern — turning recursion into an explicit stack.

The slow way first

The textbook solution is recursive: visit left, visit right, then record the node. That is clean and O(n), but it leans on the call stack, and interviewers often ask for an iterative version to see if you really understand traversal order.

The naive iterative attempt — mimic preorder with a stack — gives root → left → right, which is the wrong order. The question to ask: can I produce postorder by tweaking an order I already know how to do iteratively?

The idea: build it backwards, then reverse

Postorder is left → right → root. Read that backwards and you get root → right → left. That reversed order is just a modified preorder, and preorder is easy to do with a single stack.

So: do a preorder-style walk that visits root → right → left, but instead of appending each node, prepend it to the output. Prepending while walking in reverse order leaves the list in correct postorder.

The key insight: pushing left then right means the right child sits on top and is popped next, so we walk root → right → left — exactly the reverse of postorder.

Walk through it

Step through the animation. The pop pointer marks each node as it leaves the stack. We pop 1, then 3, then 6, then 2, 5, 4 — that is root → right → left. Each popped value is prepended to output, so by the end the list already reads [4, 5, 2, 6, 3, 1], the postorder answer.

Pseudocode

if root is empty: return []
stack = [root]
output = []
while stack is not empty:
    node = stack.pop()
    prepend node.value to output      # insert at the front
    if node has a left child:  push left
    if node has a right child: push right   # right ends up on top, pops first
return output

The Python solution

def postorder(root):
    if root is None:
        return []
    stack, output = [root], []
    while stack:
        node = stack.pop()
        output.insert(0, node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return output

• We seed the stack with the root and an empty output list.
• node = stack.pop() takes the most recently pushed node — a LIFO stack.
• output.insert(0, node.val) prepends the value; this is what reverses root→right→left into postorder.
• We push left then right, so right is on top and processed next — giving the reversed order we want.
• When the stack empties, every node has been visited after its subtrees, and output is the answer.

Complexity

One caveat: output.insert(0, ...) is O(n) per call in Python because it shifts the list. A tidier version appends each value and reverses once at the end (output[::-1]), keeping the whole thing O(n).

When this pattern shows up

Practice