Preorder traversal
Problem¶
Return a binary tree's values in preorder: root, left subtree, right subtree. Implement both recursive and iterative methods.
Key trick¶
Recursion naturally follows root-left-right; iteratively, push the right child before the left child so the stack processes the left subtree first.
Trap¶
- Pushing the left child first reverses the required traversal order.
- Appending a node after traversing its children produces a different traversal.
- Recursive depth can exceed Python's limit on a highly skewed tree.
Why is it interesting?¶
It shows how an explicit stack reproduces the call stack used by recursion.
Python solution¶
from utils import TreeNode
def preorder_recursive(root: TreeNode | None) -> list[int]:
res = []
def dfs(node: TreeNode | None) -> None:
if node is None:
return
# Preorder: process root before its subtrees.
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
def preorder_iterative(root: TreeNode | None) -> list[int]:
if root is None:
return []
res = []
stack = [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
- Time: \(O(n)\) for both methods.
- Auxiliary space: \(O(h)\) for both methods, where \(h\) is the tree height; recursive call depth may reach \(O(n)\).