What you will learn
- Implement inorder, preorder, postorder DFS both recursively and iteratively
- Implement level-order BFS using a queue
- Solve classic tree problems: max depth, invert tree, lowest common ancestor, validate BST
- Recognize which traversal order fits which problem type
Why this matters
Tree problems make up roughly 20% of coding interview questions. Unlike arrays where you can often wing it, tree problems require you to know your traversal patterns cold. The good news: once you internalize DFS and BFS templates, most tree problems become variations of the same two ideas.
Binary tree node
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = rightDFS traversals
The three DFS orders differ only in when you process the current node relative to its children.
def inorder(root):
"""Left -> Node -> Right. Gives sorted order for BSTs."""
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root):
"""Node -> Left -> Right. Useful for serialization / copying a tree."""
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root):
"""Left -> Right -> Node. Useful when you need children's results first."""
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]BFS (level-order traversal)
Process nodes level by level using a queue.
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)): # process one level at a time
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultTime: O(n) for all traversals. Space: O(n) worst case (skewed tree for DFS, full level for BFS).
Walkthrough: Maximum Depth of Binary Tree (LC 104)
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))This is postorder DFS: compute children's depths first, then combine. One line of logic.
Walkthrough: Invert Binary Tree (LC 226)
def invert_tree(root):
if not root:
return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return rootWalkthrough: Lowest Common Ancestor (LC 236)
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root # p and q are in different subtrees
return left or right # both are in the same subtreeKey insight: If both left and right recursive calls return non-None, the current node is the LCA.
Walkthrough: Validate BST (LC 98)
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi):
return False
return (is_valid_bst(root.left, lo, root.val) and
is_valid_bst(root.right, root.val, hi))Pass down valid ranges. Each node must be within (lo, hi). Left children tighten the upper bound; right children tighten the lower bound.
DFS vs. BFS: when to use which
| Problem type | Preferred traversal |
|---|---|
| Max/min depth, path sum, validate BST | DFS (recursion is natural) |
| Level-order output, shortest path in unweighted tree | BFS |
| Serialize/deserialize | Either (preorder DFS or BFS) |
| Lowest common ancestor | DFS (postorder) |
Try it yourself
- LC 104 - Maximum Depth: Implement using both DFS and BFS. Compare the code length.
- LC 102 - Binary Tree Level Order Traversal: Return the values level by level as a list of lists.
- LC 236 - Lowest Common Ancestor: Trace through a sample tree by hand to see why the algorithm works.
- LC 98 - Validate Binary Search Tree: Try the range-passing approach and the inorder-traversal approach. Which feels more natural to you?
# Complete working solutions for self-study
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a sample tree: 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
# DFS - max depth
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
print("Max depth:", max_depth(root)) # 3
# BFS - level order
def level_order(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
print("Level order:", level_order(root)) # [[3], [9, 20], [15, 7]]
# Validate BST
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi):
return False
return is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi)
print("Is valid BST:", is_valid_bst(root)) # False (3 < 9, so left child violates)Checklist
- I can implement DFS (inorder, preorder, postorder) from memory
- I can implement BFS with a queue and process nodes level by level
- I solved Maximum Depth using DFS
- I solved Level Order Traversal using BFS
- I understand the range-passing technique for validating a BST
- I can explain the Lowest Common Ancestor algorithm and why it works
Common mistakes
- Forgetting the base case: Always handle
if not root: return ...first. Missing this causesAttributeError: 'NoneType' has no attribute 'val'. - Validating BST by only checking immediate children: Checking
node.left.val < node.valis not enough. A node deep in the left subtree could still violate the BST property. You must pass down the valid range. - Modifying the tree unintentionally: In problems like LCA, make sure you're returning values up the call stack, not mutating nodes.
- Using DFS when BFS is simpler: If the problem asks for level-by-level output or shortest path, BFS is more natural and avoids the need to track depth manually.
Quick quiz
Q: In a BST with n nodes, what does an inorder traversal produce?
How to explain it in an interview
"For tree problems, I first decide between DFS and BFS. If I need level-by-level processing or shortest path, I use BFS with a queue. For most other problems like depth, path sum, or validation, I use recursive DFS. For LCA, I use postorder DFS: recurse into both subtrees, and if both return non-null, the current node is the ancestor. For BST validation, I pass a valid range (lo, hi) down the recursion and check each node falls within it."