Binary Tree Postorder Traversal: Left, Right, Root

Given the root of a binary tree, return the postorder traversal of its node values. Postorder means you visit the left subtree first, then the right subtree, then the current node.

This is LeetCode 145: Binary Tree Postorder Traversal. It completes the trio of depth-first traversals (preorder, inorder, postorder). While the recursive solution is nearly identical to the other two, the iterative version requires a different trick that is worth understanding on its own.

Example: given root = [1, null, 2, 3], the postorder traversal is [3, 2, 1].

Why this problem matters

Postorder traversal processes children before their parent. This "bottom-up" property makes it the natural choice when you need to compute something about a subtree before making a decision at the current node. Problems like deleting nodes from a tree, freeing memory in a tree structure, or evaluating an expression tree all rely on postorder logic.

It is also the third traversal order you should be able to write from memory. If you already know preorder and inorder, postorder is one line change in the recursive version. But the iterative version is different enough that it deserves its own study.

Approach 1: Recursive

The recursive solution follows the definition directly. Visit left, visit right, then process the current node.

def postorder_traversal(root):
    result = []

    def dfs(node):
        if node is None:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)

    dfs(root)
    return result

The base case if node is None: return stops recursion at leaves. The three lines after it are the entire algorithm: recurse left, recurse right, append the value. The value gets appended after both recursive calls, which is what makes this "postorder." Move the append before both calls and you get preorder. Put it between the two calls and you get inorder.

Approach 2: Iterative (reversed modified preorder)

The iterative postorder is trickier than iterative preorder or inorder. A clean approach is to observe that postorder is the reverse of a modified preorder. Normal preorder visits root, left, right. If you modify it to visit root, right, left instead, and then reverse the result, you get left, right, root, which is postorder.

def postorder_traversal(root):
    if root is None:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

The loop does a modified preorder: pop a node, record its value, then push left before right. Because a stack is LIFO, pushing left first means right gets popped first, giving root-right-left order. Reversing at the end produces left-right-root, which is postorder.

This approach avoids the complexity of tracking whether both children have been visited, which is the main difficulty in a "true" iterative postorder. The tradeoff is the final reversal, but that is O(n) and keeps the code simple.

Iterative walkthrough

Let's trace the iterative approach on the example tree [1, null, 2, 3]. The modified preorder collects [1, 2, 3], and reversing gives [3, 2, 1].

The key insight is that you are not doing postorder directly. You are doing a modified preorder (root, right, left) and then flipping the result. This is much easier to implement with a single stack than trying to track whether you have already visited both children of a node.

Complexity analysis

Time is O(n) for both approaches. Every node is visited exactly once. The reversal in the iterative approach is also O(n), so the total remains O(n).

Space is O(n) in the worst case for both. The recursive version uses O(h) call stack space where h is the height of the tree. The iterative version stores all n values in the result list and uses O(h) stack space. For a balanced tree, h = log(n). For a completely skewed tree, h = n. Since h can be as large as n, the worst-case space for both is O(n).

Edge cases

• Empty tree (root is None): return an empty list. The recursive version hits the base case immediately. The iterative version returns early before entering the loop.
• Single node (no children): return [root.val]. The recursive version calls dfs(None) twice and appends the value once. The iterative version pops the single node, appends it, and reversal of a one-element list is itself.
• Left-skewed tree (every node only has a left child): postorder visits the deepest node first and the root last. The iterative modified preorder pushes each left child and processes root first, so the reversal correctly puts the deepest node at the front.
• Right-skewed tree (every node only has a right child): same logic. The modified preorder goes root, then right, then right again. Reversal puts the deepest right node first.

The building blocks

This problem reinforces two reusable building blocks:

1. Recursive tree traversal. The pattern of if node is None: return followed by recursive calls on node.left and node.right is the foundation of nearly every tree problem. The only variation is where you place the processing step (before, between, or after the recursive calls). Mastering all three placements means you can adapt the skeleton to preorder, inorder, or postorder on demand.

2. Iterative postorder via reversed modified preorder. Instead of managing complex state to determine when both children have been visited, you flip the problem: do a modified preorder (root, right, left) and reverse the output. This trick shows up in interviews when an iterative postorder is specifically requested. The core idea, transforming a harder problem into an easier one you already know, is a pattern that extends well beyond tree traversal.

From understanding to recall

You now know two ways to perform a postorder traversal. The recursive version is three lines inside a helper: recurse left, recurse right, append. The iterative version is a modified preorder loop (push left before right, pop and record) followed by a reversal.

Understanding the reversal trick is one thing. Being able to write it under pressure is another. In an interview, you need to recall that the iterative approach uses a stack-based preorder that visits right before left, then reverses. If you hesitate on the push order or forget the reversal, the solution falls apart.

Spaced repetition locks this in. You type the solution from scratch after one day, then three days, then a week. Each repetition reinforces the push order (left first so right pops first) and the final result[::-1]. After a few rounds, iterative postorder becomes automatic.

Related posts

• Binary Tree Inorder Traversal - The second DFS traversal order, using the same recursive skeleton with the append between recursive calls
• Binary Tree Preorder Traversal - The first DFS traversal order, whose iterative version is the basis for the reversed modified preorder trick used here