DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems

A DFS LeetCode pattern guide should help you recognize when depth-first search is the right tool, choose the correct recursion template, and avoid the grid and graph bugs that cost interviews. DFS explores one path as far as possible before backtracking. It appears in tree traversal, connected components, island problems, graph reachability, cycle detection, backtracking, and path search. The core skill is not memorizing one function; it is managing state, visited markers, base cases, and complexity.

DFS LeetCode pattern guide: when to reach for DFS

Use DFS when the problem involves:

• Traversing every node in a tree or graph.
• Finding connected components.
• Exploring all paths or combinations.
• Marking reachable cells in a grid.
• Detecting cycles or dependencies.
• Computing subtree properties bottom-up.
• Backtracking through choices with undo steps.

Signals in problem wording include "islands," "regions," "connected," "path exists," "all combinations," "subsets," "permutations," "word search," "course schedule," "clone graph," and "number of components."

Before coding, ask: What are the nodes? What are the edges/neighbors? Do I need to visit every component or only search from one source? Can there be cycles? What state must be carried along the path? What should the DFS return?

The basic recursive graph template

For a graph represented as adjacency lists:

def dfs(node):
    if node in visited:
        return
    visited.add(node)

    for nei in graph[node]:
        dfs(nei)

This template is enough for reachability and component counting. For components:

components = 0
visited = set()

for node in graph:
    if node not in visited:
        components += 1
        dfs(node)

The interview explanation: "I mark a node visited before exploring neighbors so cycles do not recurse forever. I start DFS from every unvisited node because the graph may be disconnected."

Tree DFS templates

Trees have no cycles if parent pointers are absent, so you usually do not need a visited set. There are two common styles.

Preorder: process before children

def dfs(root):
    if not root:
        return
    ans.append(root.val)
    dfs(root.left)
    dfs(root.right)

Use preorder when you need to pass information down, serialize a tree, or evaluate the current node before descendants.

Postorder: process after children

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

Use postorder when the answer at a node depends on children: height, diameter, balanced tree, subtree sums, lowest common ancestor variants.

A common interview phrase: "This is a postorder DFS because I need child results before computing the current node's result."

Grid DFS template

Grid problems are graph problems where each cell is a node and neighbors are up/down/left/right, sometimes diagonals.

def dfs(r, c):
    if r < 0 or r == rows or c < 0 or c == cols:
        return
    if grid[r][c] != '1':
        return

    grid[r][c] = '0'  # mark visited

    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
        dfs(r + dr, c + dc)

For number of islands, loop over every cell. When you find land, increment count and sink/mark the whole island with DFS. You can mutate the grid if allowed; otherwise use a visited set. Mutating is memory-efficient but mention it changes input.

Grid pitfalls:

• Forgetting bounds checks before reading grid[r][c].
• Marking visited after recursive calls, causing infinite recursion between neighbors.
• Accidentally using diagonal neighbors when the problem says four-directional.
• Reusing rows and cols incorrectly on jagged input, though LeetCode grids are usually rectangular.

Backtracking DFS template

Backtracking is DFS over a decision tree. You choose an option, recurse, then undo the choice.

def backtrack(path, choices):
    if is_solution(path):
        res.append(path[:])
        return

    for choice in choices:
        if not valid(choice, path):
            continue
        path.append(choice)
        backtrack(path, next_choices)
        path.pop()

Use this for subsets, permutations, combinations, word search, N-Queens, and generate parentheses. The key is state isolation. If path is mutable, append a copy to results. If you mark a board cell visited, unmark it after the recursive call.

For combinations, pass a start index to avoid duplicates:

def dfs(start, path):
    res.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        dfs(i + 1, path)
        path.pop()

For permutations, use a used array because order matters and each element can be chosen once.

Cycle detection and three-color DFS

Directed graph cycle problems, like Course Schedule, often use three states:

• 0 = unvisited.
• 1 = visiting, currently on recursion stack.
• 2 = done, fully processed.

def has_cycle(node):
    if state[node] == 1:
        return True
    if state[node] == 2:
        return False

    state[node] = 1
    for nei in graph[node]:
        if has_cycle(nei):
            return True
    state[node] = 2
    return False

If DFS reaches a visiting node, there is a back edge and therefore a cycle. If it reaches a done node, that subgraph has already been proven safe. This is more precise than a single visited set for directed cycle detection.

For topological sort, append the node after processing neighbors, then reverse the result, or append to a stack.

Recursive vs iterative DFS

Recursive DFS is concise, but recursion depth can overflow for very deep graphs or grids. Iterative DFS uses an explicit stack:

def dfs(start):
    stack = [start]
    visited.add(start)

    while stack:
        node = stack.pop()
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                stack.append(nei)

Mark neighbors visited when pushing, not when popping, to avoid pushing the same node many times. In Python interviews, mention recursion limit if the grid can be huge. You can still code recursive DFS if constraints are moderate, but showing awareness is a plus.

Complexity analysis

For graphs, DFS is usually O(V + E) time because each vertex and edge is processed a constant number of times. Space is O(V) for visited plus recursion stack in the worst case.

For grids, time is O(rows cols) because each cell is visited at most once. Space is O(rows cols) worst-case for visited or recursion stack if the whole grid is one component.

For backtracking, complexity is often exponential because you explore a decision tree. Be specific:

• Subsets: O(2^n) results, with copying cost often O(n * 2^n).
• Permutations: O(n!) results, with copying cost O(n * n!).
• Word search: roughly O(rows cols 4^L) or 3^L after the first step because you avoid going back immediately.

Interviewers appreciate honest exponential analysis for generation problems.

Common DFS patterns by problem type

| Pattern | Problems | Key state | |---|---|---| | Tree preorder | Path sum, serialize tree | current path / accumulated value | | Tree postorder | Height, diameter, balanced tree | child return values | | Grid flood fill | Islands, surrounded regions | visited cells or mutated grid | | Connected components | Provinces, components in graph | visited set across starts | | Directed cycle | Course schedule | visiting/done state | | Backtracking | subsets, permutations, N-Queens | path plus undo step | | Path search | word search, maze | visited along current path |

Use the table mentally when choosing a template. The right template is determined by whether you need every component, child return values, cycle state, or backtracking undo.

Interview pitfalls and fixes

Pitfall: missing base case. Always stop on null node, out-of-bounds cell, visited node, or invalid choice.

Pitfall: marking visited too late. Mark before recursing into neighbors to prevent cycles.

Pitfall: global state not reset. If using class variables or outer variables, reset them per test case.

Pitfall: forgetting to copy path. res.append(path) stores a reference that later changes. Use path[:] or list(path).

Pitfall: no backtracking undo. If you mark visited for a path search, unmark it when returning if other paths may use that cell.

Pitfall: confusing graph visited with path visited. For connected components, permanent visited is correct. For all simple paths, visited may be path-local.

Pitfall: ignoring disconnected graph. Loop over all nodes if the graph may not be connected.

How to explain DFS while coding

Use this narration:

"I'll model each cell/node as a graph node. DFS will visit a node, mark it so cycles do not repeat work, and recursively explore valid neighbors. For this problem, I need to start from every unvisited node because there may be multiple components. The time complexity is linear in nodes plus edges, and the space is the visited set plus recursion stack."

For backtracking:

"This is DFS over choices. I'll add a choice, recurse, then undo it. I copy the path when I reach a solution because the list is mutable."

Clear narration helps the interviewer follow your invariants and gives them places to redirect before you code too far.

Practice plan

To build pattern recognition, solve in clusters:

1. Tree traversals: max depth, path sum, diameter, balanced tree.
2. Grid flood fill: number of islands, max area of island, surrounded regions, pacific atlantic water flow.
3. Graph traversal: clone graph, number of connected components, valid path.
4. Directed graph: course schedule, eventual safe states, topological sort.
5. Backtracking: subsets, combination sum, permutations, word search, generate parentheses.

After each problem, write down: nodes, neighbors, visited rule, return value, and complexity. That reflection is what turns individual solutions into a reusable DFS pattern.

DFS is powerful because it gives you a disciplined way to explore structure. Identify the graph, choose the right state, mark visits at the right time, and be explicit about whether state is global, per component, or per path. Those choices are the interview.

DFS vs BFS: choosing the traversal

DFS and BFS both traverse graphs, but they fit different interview needs. DFS is natural when you need to explore a whole component, compute recursive structure, or backtrack through choices. BFS is usually better for shortest path in an unweighted graph because it explores level by level. If the problem asks for "minimum number of steps," "nearest," or "shortest transformation," start by considering BFS. If it asks for "all paths," "connected regions," "subtree result," or "can this path exist," DFS is often simpler.

A good interview phrase: "BFS would find the shortest path here, but since the problem only asks whether a path exists, DFS is sufficient and simpler." Or the reverse: "DFS can find a path, but not necessarily the shortest one in an unweighted graph, so I would use BFS."

Dry-run discipline

Before submitting a DFS solution, dry-run one small cyclic or boundary case. For a grid, try a 2x2 island and confirm each land cell is marked once. For a graph, try 0 -> 1 -> 0 and confirm visited prevents infinite recursion. For backtracking, try two numbers and confirm path.pop() restores state for the next branch. This 30-second dry run catches most DFS bugs.

Also check empty input: empty grid, null root, no courses, one node, or a word longer than the board capacity. Interviewers notice when you protect these cases before running code.

Related guides

• Graph Algorithms LeetCode Pattern Guide — DFS, BFS, Dijkstra, and Union-Find — A practical graph algorithms LeetCode pattern guide covering DFS, BFS, Dijkstra, union-find, topological sort, grid graphs, and interview explanation patterns. Use it to identify the graph shape before choosing the algorithm.
• Divide and Conquer LeetCode Pattern Guide — Merge Sort, Quickselect, and Recursion — A practical LeetCode pattern guide for divide and conquer: master recursive contracts, merge sort variations, quickselect, tree recursion, complexity, and common interview traps.
• Dynamic Programming LeetCode Pattern Guide — Knapsack, LIS, and Interval DP Templates — A pattern-first DP guide for LeetCode interviews, with recognition rules, knapsack, LIS, interval DP templates, loop-order traps, and interview narration.
• LeetCode Patterns Cheatsheet: 15 Templates That Solve 80% of Problems — Stop grinding blindly. These 15 reusable patterns cover the vast majority of LeetCode problems and will cut your prep time in half.
• Monotonic Stack LeetCode Pattern Guide — Next Greater Element and Histogram Problems — Learn the monotonic stack pattern for next greater element, daily temperatures, stock spans, and largest rectangle in histogram problems, with templates and interview traps.