BFS & DFS

Tree and graph traversal, grids, shortest paths in unweighted graphs.

Breadth-first and depth-first search are how you traverse trees, graphs and grids. They appear in more interview questions than any other pattern. The key is knowing which one fits, and writing each from memory without bugs.

BFS or DFS?

Trees

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

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 exactly one level
            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

Most tree problems are DFS where you decide what each call returns and how a node combines its children's results. Lowest common ancestor, diameter, path sums and balanced-tree checks all follow that shape.

Graphs

Graphs need a visited set — trees don't have cycles, graphs do.

from collections import deque

def shortest_path(graph, start, goal):
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == goal:
            return dist
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)          # mark when enqueued, not when popped
                queue.append((nxt, dist + 1))
    return -1

Grids

Treat each cell as a node with up to 4 neighbors:

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            sink(r + dr, c + dc)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

Multi-source BFS — start the queue with *all* sources at distance 0 (e.g. "rotting oranges", "distance to nearest gate").

Pitfalls

Marking visited when popping instead of when pushing — nodes get enqueued many times
Deep recursion on large grids — mention the recursion limit and offer an iterative version
Mutating the input grid without asking — say "I'll mark visited in place; I can use a set if we can't modify the input"

[!TIP] Practice Number of Islands · Binary Tree Right Side View · Lowest Common Ancestor