DFS, BFS & Backtracking

These patterns are your toolkit for exploring trees, graphs, and generating all possible combinations. They appear in a wide range of interview problems.

DFS (Depth-First Search)

DFS explores as deep as possible before backtracking. It uses a stack (or recursion's call stack).

When to Use DFS:

• Tree traversals (preorder, inorder, postorder)
• Path finding in graphs
• Connected components
• Cycle detection

# Number of islands (classic DFS)
def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # Mark visited
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

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

# Path sum in binary tree
def has_path_sum(root, target_sum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target_sum
    return (has_path_sum(root.left, target_sum - root.val) or
            has_path_sum(root.right, target_sum - root.val))

BFS (Breadth-First Search)

BFS explores level by level using a queue. It guarantees the shortest path in unweighted graphs.

When to Use BFS:

• Shortest path (unweighted graph)
• Level-order traversal
• Minimum steps/moves problems
• Nearest neighbor searches

from collections import deque

# Shortest path in binary matrix
def shortest_path(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

    while queue:
        r, c, dist = queue.popleft()
        if r == n-1 and c == n-1:
            return dist
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return -1

DFS vs BFS Decision

Criteria	DFS	BFS
Shortest path	No (in general)	Yes (unweighted)
Memory usage	O(h) height	O(w) width
Implementation	Recursion or stack	Queue
Best for trees	Path problems	Level-order
Best for graphs	Connected components	Shortest distance

Backtracking

Backtracking is DFS with a twist: you build a solution incrementally and abandon it ("backtrack") when it can't lead to a valid result.

The Template:

def backtrack(candidates, path, result, start):
    if is_valid_solution(path):
        result.append(path[:])  # Add copy
        return
    for i in range(start, len(candidates)):
        path.append(candidates[i])       # Choose
        backtrack(candidates, path, result, i + 1)  # Explore
        path.pop()                        # Un-choose (backtrack)

Classic Backtracking Problems:

# Subsets: generate all subsets of a set
def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

# Permutations
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], nums)
    return result

# N-Queens
def solve_n_queens(n):
    result = []
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            board[row][col] = 'Q'
            backtrack(row+1, cols|{col}, diag1|{row-col}, diag2|{row+col}, board)
            board[row][col] = '.'
    board = [['.']*n for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return result

Interview Tip: Backtracking problems follow a "choose, explore, un-choose" pattern. If you can identify this structure, the solution writes itself.

---

Next, the pattern that strikes fear into most candidates: dynamic programming. :::