Tree Patterns

The reusable skeletons behind every tree problem. Learn these once, solve them all.

▶ Decision Framework

When do I use BFS vs DFS?

▸ BFS (Breadth-First)

Need values level by level (#102, #103, #107)
Need the shortest path or first leaf (#111 iterative)
Comparing trees in lockstep (#100, #572 iterative)
State lives in an explicit queue

▸ DFS (Depth-First)

Computing a bottom-up value (depth, equality)
Need to aggregate results from subtrees (#104, #111)
Collecting values with a level index (#102, #103, #107 recursive)
State lives in the call stack

▶ BFS vs DFS Decision Flowchart

Tree Problem

→

Need levels?

YES→

BFS + Queue

NO↓

Bottom-up value?

YES→

Recursive DFS

NO↓

Compare structure?

YES→

BFS/DFS with pairs

NO↓

Recursive DFS

Iterative vs Recursive — what's the real difference?

They're the same algorithm with different state storage. Neither is "better" — interviewers want to see you can do both.

Iterative

You manage a queue or stack explicitly
State is visible — you can inspect it
Easier to animate step by step
Uses O(n) heap memory

Recursive

The call stack manages state for you
State is implicit — hidden in stack frames
Often shorter and more elegant code
Uses O(h) stack memory (h = tree height)

Interview tip: Start with whichever feels natural, then offer to show the other. Saying "I can also do this iteratively with a queue" signals depth.

◆ Universal Patterns

Pattern 1: The Null Check Trinity all problems

Nearly every recursive tree solution starts with 1–3 null checks. Recognise the shape and you've solved the first half.

# Base case — empty tree if not root: return 0 # or [], True, False — depends on problem # Single-child guard (depth problems) if not root.left: # only right subtree exists return 1 + self.minDepth(root.right) # Two-tree comparison (#100 Same Tree) if not p and not q: # both null → match return True if not p or not q: # one null → mismatch return False

Muscle memory: Before writing anything else, ask yourself: "What happens when the node is null?"

Pattern 2: Level Index Trick DFS

The shared skeleton behind #102, #103, and #107. One DFS with a level parameter, three different results.

def traverse(self, root): result = [] def dfs(node, level): if not node: return if level == len(result): # ← first node at this depth result.append(???) # ← [] or deque() result[level].???(node.val) # ← append or appendleft dfs(node.left, level + 1) dfs(node.right, level + 1) dfs(root, 0) return ??? # ← result, result[::-1], or convert

Fill in the ??? slots for each problem:

#102 → append([]), .append(val), return result
#103 → append(deque()), parity check for .append vs .appendleft, return [list(d) for d in result]
#107 → append([]), .append(val), return result[::-1]

Pattern 3: Deque Power Moves BFS & DFS

from collections import deque — this one import unlocks O(1) operations at both ends.

BFS Queue

q = deque([root]) node = q.popleft()

O(1) popleft vs O(n) list.pop(0)

Zigzag Level

level = deque() level.appendleft(val)

O(1) insert at front for R←L

Bottom-Up

result = deque() result.appendleft(lvl)

O(1) prepend vs O(n) insert(0)

Rule of thumb: If you ever write list.pop(0), list.insert(0, x), or list.reverse(), ask yourself if a deque eliminates the O(n) cost.

Pattern 4: Post-Order Aggregation DFS

For problems that compute a value from subtrees (depth, diameter, balance), the skeleton is always post-order: recurse first, combine after.

def solve(self, root): if not root: return 0 left = self.solve(root.left) # recurse left right = self.solve(root.right) # recurse right return 1 + ???(left, right) # combine

#104 Max Depth → max(left, right)
#111 Min Depth → min(left, right) + single-child guards before recursing

The single-child guard in #111 prevents counting a path that ends at a non-leaf (e.g., a node with only one child isn't a valid "minimum depth" endpoint).