LeetCode 144: Binary Tree Preorder Traversal Solution in Python Explained

Traversing a binary tree in preorder might feel like exploring a family tree starting from the root, and LeetCode 144: Binary Tree Preorder Traversal is an easy-level challenge that makes it straightforward! Given the root of a binary tree, you need to return the preorder traversal of its nodes’ values—a list where each node is visited before its left and right subtrees (root, left, right). In this blog, we’ll solve it with Python, exploring two solutions—Recursive Preorder (our best solution) and Stack-Based Preorder (a practical alternative). With step-by-step examples, detailed code breakdowns, and tips, you’ll master this problem. Let’s traverse that tree!

Problem Statement

Section link icon

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

Section link icon

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

Section link icon

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

Section link icon

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

Section link icon

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

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

Edge Cases

Section link icon
  • Empty Tree: [][].
  • Single Node: [1][1].
  • Left Skewed: [1,2,3][1,2,3].

Both solutions handle these well.

Final Thoughts

Section link icon

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!