Binary Tree Postorder Traversal

Difficulty: Easy Source: NeetCode

Problem

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1: Input: root = [1,null,2,3] Output: [3,2,1]

Example 2: Input: root = [] Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary Trees — Hierarchical data structure where each node has at most two children
• Recursion — Solving subproblems by calling the function on smaller inputs
• Stack — LIFO structure useful for reversing traversal order iteratively

1. Recursive DFS

Intuition

Postorder means left → right → root. You process both subtrees fully before visiting the current node. This is the natural order for deletion (delete children before parent) or for bottom-up computations.

Algorithm

1. If the current node is null, return
2. Recurse on the left child
3. Recurse on the right child
4. Append the current node’s value to the result

Solution

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

def postorder_recursive(root):
    result = []

    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)  # Visit root last

    dfs(root)
    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, None, 2, 3])
print(postorder_recursive(root1))  # [3, 2, 1]

root2 = build_tree([])
print(postorder_recursive(root2))  # []

root3 = build_tree([1, 2, 3, 4, 5])
print(postorder_recursive(root3))  # [4, 5, 2, 3, 1]

Complexity

• Time: O(n) — every node is visited exactly once
• Space: O(h) — call stack depth equals tree height

2. Iterative (Reverse Preorder Trick)

Intuition

Postorder (left → right → root) is the exact reverse of a modified preorder (root → right → left). So we do a preorder variant — pushing left before right — collect the result, and then reverse it at the end. It’s a neat trick that avoids the complexity of the “true” iterative postorder with two stacks.

Algorithm

1. Use a stack starting with root
2. While the stack is not empty:
   • Pop a node and prepend (or collect then reverse) its value
   • Push the left child first, then the right child
3. Reverse the collected values and return

Solution

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

def postorder_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push left first, then right
        # (right will be processed next → root, right, left order)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    # Reversing gives left, right, root = postorder
    return result[::-1]

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, None, 2, 3])
print(postorder_iterative(root1))  # [3, 2, 1]

root2 = build_tree([])
print(postorder_iterative(root2))  # []

root3 = build_tree([1, 2, 3, 4, 5])
print(postorder_iterative(root3))  # [4, 5, 2, 3, 1]

Complexity

• Time: O(n) — every node processed once, plus O(n) for the reverse
• Space: O(n) — result list stores all values before reversing

Common Pitfalls

Forgetting the reversal. The iterative trick only works if you remember to reverse the collected list at the end. Without it you get a root→right→left traversal, not postorder.

Confusing with inorder. Inorder and postorder both visit the root last-ish, but the difference is that inorder visits root between the two subtrees. Keep the mnemonic: “post” = root comes after everything.