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
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!