LeetCode 144: Binary Tree Preorder Traversal Solution in Python Explained

Problem Statement

In LeetCode 144, you’re given the root of a binary tree. Your task is to return a list of node values in preorder traversal order: visit the root, then the left subtree, then the right subtree. This contrasts with list reordering like LeetCode 143: Reorder List, focusing on tree traversal rather than structural modification.

Constraints

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

Example

Let’s see some cases:

Input: root = [1,null,2,3]
      1
       \
        2
       /
      3
Output: [1,2,3]
Explanation: Root (1), left (none), right (2->3).

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

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

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

Understanding the Problem

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

Let’s dive into the best solution.

Best Solution: Recursive Preorder Approach

Explanation

Recursive Preorder uses the natural recursive structure of a binary tree: visit the root, then recursively traverse the left subtree, followed by the right subtree, appending values to a result list. It’s the best solution due to its O(n) time complexity, simplicity, and alignment with preorder’s definition, making it intuitive and efficient for tree traversal.

For [1,null,2,3]:

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

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 [1,2,3].

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

Example 2: root = []

Goal: Return [].

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

Example 3: root = [1]

Goal: Return [1].

• Start: result = [], preorder(1).
• Step 1: root = 1.
• Append 1, result = [1].
• Left: None, Right: None, skip.
• Finish: Return [1].

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

Here’s the Python code with a thorough breakdown:

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

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

    # Line 2: Define recursive helper function
    def preorder(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 1), return
            return

        # Line 4: Visit current node (root)
        result.append(node.val)
        # Adds root value first (e.g., 1, result=[1])

        # Line 5: Traverse left subtree
        preorder(node.left)
        # Recursively visits left (e.g., None for root=1)

        # Line 6: Traverse right subtree
        preorder(node.right)
        # Recursively visits right (e.g., 2, then 3)
        # e.g., result=[1,2,3]

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

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

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

Alternative: Stack-Based Preorder Approach

Explanation

Stack-Based Preorder uses a stack to mimic recursion iteratively, pushing the root, popping and appending its value, then pushing right and left children (right first to process left before right). It’s a practical alternative, also O(n) time, but uses O(h) space for the stack, offering explicit control over traversal order.

For [1,null,2,3]:

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

Step-by-Step Example (Alternative)

For [1,null,2,3]:

• Start: stack = [1], result = [].
• Step 1: Pop 1, append 1, push 2, result = [1], stack = [2].
• Step 2: Pop 2, append 2, push 3, result = [1,2], stack = [3].
• Step 3: Pop 3, append 3, result = [1,2,3], stack = [].
• Finish: Return [1,2,3].

How the Code Works (Stack-Based)

def preorderTraversalStack(root: TreeNode) -> list[int]:
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

Complexity

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

Efficiency Notes

Recursive Preorder is the best solution with O(n) time and O(h) space, offering simplicity and natural tree traversal—Stack-Based Preorder matches complexity, providing an iterative alternative that’s useful for avoiding recursion limits, though slightly more complex to implement.

Key Insights

• Preorder: Root, left, right.
• Recursion: Natural for trees.
• Stack: Iterative control.

Additional Example

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

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

Edge Cases

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

Both solutions handle these well.

Final Thoughts

LeetCode 144: Binary Tree Preorder Traversal in Python is a foundational tree traversal challenge. The Recursive Preorder solution stands out for its efficiency and clarity, while Stack-Based Preorder offers an iterative twist. Want more? Try LeetCode 94: Binary Tree Inorder Traversal for inorder or LeetCode 143: Reorder List for list manipulation. Ready to practice? Solve LeetCode 144 on LeetCode with [1,null,2,3], aiming for [1,2,3]—test your skills now!