What you will learn
- The one question that solves most tree DFS problems: what does each call return?
- Level-order BFS with a queue snapshot.
- Passing bounds down to validate a BST.
Signals
- Binary tree or n-ary tree input.
- “Depth”, “path”, “diameter”, “balanced”, “lowest common ancestor” → DFS.
- “Level”, “right side view”, “zigzag”, “minimum depth” → BFS.
DFS: decide what each call returns
Write the function for one node, assuming the recursive calls on children already return correct answers. Then combine. Sometimes the value you return differs from the value you track globally: in maximum path sum, a call returns the best path going down from the node, while the global best may bend through the node using both children.
BFS: process level by level
Use a queue; at the start of each level, take len(q) as the number of nodes on this level. That snapshot is how you separate levels without storing depths.
Code
"""Tree DFS and BFS: depth, path sums, level order, validating a BST."""
from collections import deque
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def from_list(values):
"""Build a tree from level-order values with None for gaps (LeetCode style)."""
if not values:
return None
it = iter(values)
root = TreeNode(next(it))
q = deque([root])
for left in it:
node = q.popleft()
right = next(it, None)
if left is not None:
node.left = TreeNode(left)
q.append(node.left)
if right is not None:
node.right = TreeNode(right)
q.append(node.right)
return root
def max_depth(node):
if node is None:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
def max_path_sum(root):
best = float("-inf")
def gain(node): # best downward path starting at node
nonlocal best
if node is None:
return 0
left, right = max(gain(node.left), 0), max(gain(node.right), 0)
best = max(best, node.val + left + right) # path that bends at this node
return node.val + max(left, right)
gain(root)
return best
def level_order(root):
out, q = [], deque([root] if root else [])
while q:
level = []
for _ in range(len(q)): # snapshot: exactly this level's nodes
node = q.popleft()
level.append(node.val)
q.extend(c for c in (node.left, node.right) if c)
out.append(level)
return out
def is_valid_bst(node, lo=float("-inf"), hi=float("inf")):
if node is None:
return True
if not lo < node.val < hi:
return False
return is_valid_bst(node.left, lo, node.val) and is_valid_bst(node.right, node.val, hi)
if __name__ == "__main__":
t = from_list([-10, 9, 20, None, None, 15, 7])
print(max_depth(t), max_path_sum(t), level_order(t))
print(is_valid_bst(from_list([5, 1, 8, None, None, 6, 9])), is_valid_bst(from_list([5, 1, 8, None, None, 3, 9])))
Output:
3 42 [[-10], [9, 20], [15, 7]]
True False
max_path_sumis 42: the path 15 → 20 → 7. Negative child gains are clipped to 0 (“don’t take that branch”).is_valid_bstpasses the allowed(lo, hi)range down. The second tree fails because 3 is in the right subtree of 5, even though it’s a valid left child of 8. Checking only parent-child pairs misses this, which is the classic bug.from_listbuilds trees from LeetCode-style arrays so you can test quickly.
Traversal orders
- Pre-order (node, left, right): copy or serialise a tree.
- In-order (left, node, right): sorted order of a BST; k-th smallest.
- Post-order (left, right, node): when the parent needs children’s results first (heights, path sums, deletes).
Recursion depth equals tree height; for very deep (skewed) trees, use an explicit stack or raise Python’s recursion limit.
Practise: tree DFS, tree BFS and BST problems.
Key takeaways
- For DFS, define what a call returns for one node, trust the recursion for children, combine.
- Track a global answer separately when it can bend through a node.
- BFS by level: snapshot the queue size at the start of each level.
- Validate a BST with bounds passed down, not parent-child comparisons.
Exercises
- Diameter of a binary tree (longest path between any two nodes).
- Right side view using BFS (last node of each level).
- Lowest common ancestor of two nodes in a binary tree.
Quiz
- In
max_path_sum, why doesgainreturnnode.val + max(left, right)instead of both sides? - How does BFS know where one level ends?
- Why does checking
left.val < node.val < right.valfail to validate a BST?
Show answers
- A path continuing up to the parent can use only one branch; the bending path using both is recorded in
bestbut can’t be extended. - It records the queue length at the start of the level and pops exactly that many nodes.
- It only checks direct children; a deeper node can still violate an ancestor’s bound (like 3 under 5’s right subtree).