Postorder traversal

Problem¶

Return a binary tree's values in postorder: left subtree, right subtree, then root.

Tree:       1
             \
              2
             /
            3

Postorder: [3, 2, 1]

Implement both recursive and iterative traversals.

Key trick¶

Recursion naturally delays each node until both subtrees are processed; iteratively, store a visited flag to simulate that return point.

Trap¶

• Appending the root before traversing both children produces preorder or inorder.
• In the iterative version, children must be pushed in reverse processing order because the stack is LIFO.
• Deep skewed trees can exceed Python's recursion limit.

Why is it interesting?¶

It tests tree traversal fundamentals and the ability to translate recursive call-stack behavior into an explicit stack.

Python solution¶

from utils import TreeNode


def postorder_recursive(root: TreeNode | None) -> list[int]:
    res = []

    def dfs(node):
        if node is None:
            return

        dfs(node.left)
        dfs(node.right)
        res.append(node.val)

    dfs(root)
    return res


def postorder_iterative(root: TreeNode | None) -> list[int]:
    if root is None:
        return []

    res = []
    stack = [(root, False)]

    while stack:
        node, expanded = stack.pop()

        if not expanded:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
            continue

        res.append(node.val)

    return res

• Time: \(O(n)\) for both versions.
• Space: \(O(h)\) for recursion and \(O(n)\) for the iterative version, where \(h\) is the tree height.