LeetCode 145: Binary Tree Postorder Traversal Solution in Python Explained

Problem Statement

In LeetCode 145, you’re given the root of a binary tree. Your task is to return a list of node values in postorder traversal order: visit the left subtree, then the right subtree, then the root. This contrasts with preorder traversal in LeetCode 144: Binary Tree Preorder Traversal, where the root comes first, and differs from list reordering like LeetCode 143: Reorder List.

Constraints

• Number of nodes: 0 <= n <= 100
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

Copy codeInput: root = [1,null,2,3]
      1
       \
        2
       /
      3
Output: [3,2,1]
Explanation: Left (3), right (none), root (2), then root (1).

Copy codeInput: root = []
Output: []
Explanation: Empty tree, no nodes.

Copy codeInput: root = [1]
Output: [1]
Explanation: Single node, just root.

These examples show we’re collecting values in postorder: left, right, root.

Understanding the Problem

How do you solve LeetCode 145: Binary Tree Postorder Traversal in Python? Take root = [1,null,2,3]. We need [3,2,1]—visit left (3), right (none), root (2), then root (1). For an empty tree, return []. This builds on LeetCode 94: Binary Tree Inorder Traversal, changing the order to left-right-root, and isn’t a cycle detection task like LeetCode 142: Linked List Cycle II. We’ll use: 1. Recursive Postorder: O(n) time, O(h) space—our best solution. 2. Stack-Based Postorder: O(n) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive Postorder Approach

Explanation

Recursive Postorder leverages the recursive nature of a binary tree: traverse the left subtree, then the right subtree, and finally visit the root, appending values to a result list. It’s the best solution due to its O(n) time complexity, simplicity, and direct alignment with postorder’s definition, making it both intuitive and efficient for tree traversal.

For [1,null,2,3]:

• Left: 3.
• Right: none.
• Root: 2, then 1.
• Result: [3,2,1].

Step-by-Step Example

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

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

Goal: Return [3,2,1].

• Start: result = [], postorder(root=1).
• Step 1: root = 1.
• Left: postorder(None) → skip.
• Right: postorder(2).
• Left: postorder(3).
• Left: None, Right: None, append 3, result = [3].
• Right: None, append 2, result = [3,2].
• Append 1, result = [3,2,1].
• Finish: Return [3,2,1].

Example 2: root = []

Goal: Return [].

• Start: result = [], postorder(None).
• Step 1: Null root, skip.
• Finish: Return [].

Example 3: root = [1]

Goal: Return [1].

• Start: result = [], postorder(1).
• Step 1: root = 1.
• Left: None, Right: None, append 1, result = [1].
• Finish: Return [1].

How the Code Works (Recursive Postorder) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def postorderTraversal(root: TreeNode) -> list[int]:
    # Line 1: Initialize result list
    result = []
    # Stores postorder values (e.g., initially [])

    # Line 2: Define recursive helper function
    def postorder(node: TreeNode):
        # node = current node (e.g., root=1)

        # Line 3: Base case - check if node exists
        if not node:
            # If node is None (e.g., left of 2), return
            return

        # Line 4: Traverse left subtree
        postorder(node.left)
        # Recursively visits left (e.g., 3, appends 3 first)

        # Line 5: Traverse right subtree
        postorder(node.right)
        # Recursively visits right (e.g., None for 2)

        # Line 6: Visit current node (root)
        result.append(node.val)
        # Adds root value last (e.g., 2, then 1)
        # e.g., result=[3,2,1]

    # Line 7: Start traversal from root
    postorder(root)
    # Initiates with root (e.g., 1)

    # Line 8: Return postorder traversal
    return result
    # Final list (e.g., [3,2,1])

This detailed breakdown clarifies how recursive postorder efficiently traverses the tree.

Alternative: Stack-Based Postorder Approach

Explanation

Stack-Based Postorder uses a stack to iteratively traverse the tree, pushing nodes and tracking the last visited node to append values in left-right-root order. It processes left children first, then right, appending the root after both subtrees. This is a practical alternative, also O(n) time, but uses O(h) space, offering control over traversal without recursion.

For [1,null,2,3]:

• Push 1, 2, 3.
• Pop 3, append 3.
• Pop 2, append 2.
• Pop 1, append 1.
• Result: [3,2,1].

Step-by-Step Example (Alternative)

For [1,null,2,3]:

• Start: stack = [1], result = [], prev = None.
• Step 1: Peek 1, push 2, stack = [1,2].
• Step 2: Peek 2, push 3, stack = [1,2,3].
• Step 3: Pop 3 (no children), append 3, result = [3], prev = 3.
• Step 4: Pop 2 (left done), append 2, result = [3,2], prev = 2.
• Step 5: Pop 1 (right done), append 1, result = [3,2,1].
• Finish: Return [3,2,1].

How the Code Works (Stack-Based)

Copy codedef postorderTraversalStack(root: TreeNode) -> list[int]:
    if not root:
        return []
    stack = [root]
    result = []
    prev = None
    while stack:
        curr = stack[-1]
        if not prev or prev.left == curr or prev.right == curr:
            if curr.left:
                stack.append(curr.left)
            elif curr.right:
                stack.append(curr.right)
        elif curr.left == prev:
            if curr.right:
                stack.append(curr.right)
        else:
            result.append(curr.val)
            stack.pop()
            prev = curr
    return result

Complexity

• Recursive Postorder:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Stack-Based Postorder:
• Time: O(n) – visits each node once.
• Space: O(h) – stack size.

Efficiency Notes

Recursive Postorder is the best solution with O(n) time and O(h) space, offering simplicity and natural traversal—Stack-Based Postorder matches complexity, providing an iterative alternative that’s more complex but avoids recursion limits.

Key Insights

• Postorder: Left, right, root.
• Recursion: Bottom-up visits.
• Stack: Iterative with tracking.

Additional Example

For root = [1,2,3,4,5]:

• Goal: [4,5,2,3,1].
• Recursive: 4, 5, 2, 3, 1.

Edge Cases

• Empty Tree: [] → [].
• Single Node: [1] → [1].
• Right Skewed: [1,null,2,null,3] → [3,2,1].

Both solutions handle these well.

Final Thoughts

LeetCode 145: Binary Tree Postorder Traversal in Python is a key traversal challenge. The Recursive Postorder solution excels with its efficiency and clarity, while Stack-Based Postorder offers an iterative approach. Want more? Try LeetCode 144: Binary Tree Preorder Traversal for preorder or LeetCode 143: Reorder List for list skills. Ready to practice? Solve LeetCode 145 on LeetCode with [1,null,2,3], aiming for [3,2,1]—test your skills now!