How to Solve Preorder Traversal on LeetCode
The Preorder Traversal problem is a fundamental binary tree challenge on LeetCode, often asked to test understanding of recursion and stack-based tree traversal.
Problem Statement
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Preorder means: visit the root, then left subtree, then right subtree.
Example:
Input: root = [1,null,2,3]
Output: [1,2,3]
Why This Problem Matters for Interviews
This problem:
- Tests knowledge of tree structure and depth-first search (DFS)
- Checks your ability to code both recursive and iterative solutions
- Sets the stage for harder tree/graph algorithms
Approaches to Preorder Traversal
1. Recursive DFS
Time Complexity: O(n)
Space Complexity: O(n) for call stack in worst case
def preorderTraversal(root):
res = []
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
2. Iterative with Stack
Time Complexity: O(n)
Space Complexity: O(n)
def preorderTraversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
Key Interview Talking Points
- Difference between preorder, inorder, and postorder.
- Why recursion naturally models tree traversal.
- How iterative stack mirrors recursion.
- Space usage in worst case (skewed trees).
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive | O(n) | O(n) |
| Iterative Stack | O(n) | O(n) |
Pro Interview Tips
- Draw the tree and walk through traversal by hand.
- Mention that preorder is root-first; contrast with inorder/postorder.
- Practice with test cases