DFS Pattern Recognition: Every Problem Leaves the Same Five Clues

You've read the DFS explanation. Arrow bounces through a graph, visits nodes, backtracks. You nod along. Totally get it.

Then the interview asks you to find the diameter of a binary tree and you stare at the screen for thirty seconds wondering if diameter means BFS.

The hard part of DFS in interviews is never the implementation. It's pattern recognition: figuring out which variant the problem wants, because picking the wrong one gets you a correct solution to the wrong problem. So here's the map.

Five Signals for DFS Pattern Recognition

Problems don't say "use DFS." They say things like "count the number of islands," "determine if all courses can be finished," or "find the diameter of a binary tree." Each phrase points at a specific variant. Learn to hear the signal before you write a single line.

Signal 1: Tree or grid structure, no shortest-path requirement. If the input is a binary tree, an N-ary tree, or a 2D grid and the problem doesn't ask for minimum steps or minimum depth, start with DFS. The recursion naturally mirrors the structure, and BFS's level-order machinery buys you nothing here.

Signal 2: "Count connected regions" or "how many islands." This is the flood-fill family. An outer loop finds each new unvisited starting point, and DFS consumes the entire component before the loop continues. The component count comes from counting how many times the outer loop triggers DFS, not from inside DFS itself.

Signal 3: "Does a path exist" or "find all paths." DFS commits fully to one branch before trying the next. For existence, return true the moment you hit the target. For all paths, collect each complete path and then backtrack. The two sub-variants have completely different code, so pick the right one before you type.

Signal 4: "Detect a cycle" or "check for valid ordering." Course Schedule, alien dictionary, task dependencies. If a problem mentions prerequisites, ordering constraints, or "determine if possible," you're almost certainly writing DFS cycle detection. Topological sort is cycle detection with a post-order collection step.

Signal 5: "Compute a property of each subtree." Height, diameter, subtree sum, balance check. These depend on children's results before you can compute the current node's answer. That's postorder DFS. Using preorder here produces wrong answers, and they'll be confidently, silently wrong.

The Two Core Templates

Graph and grid DFS. The structure can have cycles, so you need a visited set.

def dfs(node, graph, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

visited = set()
for node in graph:
    if node not in visited:
        dfs(node, graph, visited)

The outer loop is not optional. A single dfs(start, ...) call misses every component that isn't connected to start. This is one of the most common interview mistakes on disconnected graph problems. You get a working DFS function, you start it on node zero, you feel great, and then you return the wrong answer because forty percent of the graph never got visited.

When you call DFS once on node 0 and confidently return your answer, not knowing there are four more disconnected components waiting.

For grids, replace graph[node] with the four neighbors (row±1, col) and (row, col±1). A common shortcut is marking cells in place (set grid[row][col] = '#') instead of maintaining a separate visited set. Ask before mutating input.

def flood(grid, r, c):
    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
        return
    if grid[r][c] != '1':
        return
    grid[r][c] = '#'
    flood(grid, r + 1, c)
    flood(grid, r - 1, c)
    flood(grid, r, c + 1)
    flood(grid, r, c - 1)

count = 0
for r in range(len(grid)):
    for c in range(len(grid[0])):
        if grid[r][c] == '1':
            flood(grid, r, c)
            count += 1

Tree DFS. No visited set needed. The only decision is order: process this node before or after its children?

# Preorder: this node, then children
def preorder(node, accumulated):
    if not node:
        return
    use(accumulated, node.val)          # node available immediately
    preorder(node.left, updated)
    preorder(node.right, updated)

# Postorder: children first, then this node
def postorder(node):
    if not node:
        return 0
    left = postorder(node.left)
    right = postorder(node.right)
    return combine(left, right, node.val)   # children results available

Use preorder when what you compute depends only on information passed down from ancestors: path sums, current depth, accumulated constraints. Use postorder when the node's result depends on its children: height, subtree sum, balance validation.

Two States Aren't Enough for Directed Graphs

This is the trap that catches people on Course Schedule and every "detect cycle in directed graph" variant.

For undirected graphs, a boolean visited set works. Hit a node you've already seen? Cycle.

In directed graphs, that logic is wrong. Consider edges A → B and C → B. You visit B from A, mark it visited. Then C tries to visit B and finds it already marked. Is that a cycle? No. Two nodes just point at the same target. A boolean visited set flags this as a cycle, and it's not.

Directed graph cycle detection needs three states, following the three-color scheme from CLRS: white (unvisited), gray (currently on the call stack), black (fully processed).

WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(node, color, adj):
    color[node] = GRAY
    for neighbor in adj[node]:
        if color[neighbor] == GRAY:
            return True          # back edge: neighbor still on the stack
        if color[neighbor] == WHITE:
            if has_cycle(neighbor, color, adj):
                return True
    color[node] = BLACK
    return False

color = [WHITE] * n
for node in range(n):
    if color[node] == WHITE:
        if has_cycle(node, color, adj):
            return False        # cycle found, topological order impossible

Gray means "I'm currently inside this node's subtree." Finding a gray node during exploration means you've reached an ancestor still on the stack. That's a back edge, and back edges are what make cycles in directed graphs. Black means finished, done, safe. Merging gray and black into a single "visited" bucket loses path-membership information. Your code looks right, handles the simple test cases, and silently fails on the diamond-shaped graph the interviewer is about to draw.

The Hardest Pattern: Return Height, Track Diameter

Some DFS problems require the function to return one value to its parent while updating a global answer with something different inside the same call. This is the pattern with the highest failure rate, and it looks innocent right up until your answer is wrong.

Diameter of Binary Tree (LC 543): The diameter through any node is left_height + right_height. But the function can only return a single number to its parent, because a tree path can't fork. So it returns height for the parent's benefit, while recording left + right as a diameter candidate before returning.

def diameter_of_binary_tree(root: TreeNode) -> int:
    best = [0]

    def height(node):
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best[0] = max(best[0], left + right)    # update global: can fork here
        return 1 + max(left, right)             # return to parent: single path only

    height(root)
    return best[0]

Binary Tree Maximum Path Sum (LC 124) is the same skeleton. Negative children get clamped to zero, because including a negative-value subtree makes the path worse:

def max_path_sum(root: TreeNode) -> int:
    best = [root.val]

    def gain(node):
        if not node:
            return 0
        left = max(0, gain(node.left))      # discard if negative
        right = max(0, gain(node.right))
        best[0] = max(best[0], left + node.val + right)
        return node.val + max(left, right)

    gain(root)
    return best[0]

You told the function to return height. It returned height. You wanted it to also track the diameter globally. This is a communication problem, not a code problem.

Recognize it by this shape: the best answer forks at some node, but the parent can only continue in one direction. You need a split between what you return and what you track globally. Returning the forked value directly cascades wrong heights upward and everything breaks quietly.

Backtracking DFS: Undo Your Marks

Word Search (LC 79) is DFS with one extra requirement: the visited state must be undone after each branch, because two different exploration paths might need the same cell.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[i]:
            return False

        tmp = board[r][c]
        board[r][c] = '#'                   # mark: this cell is in the current path

        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))

        board[r][c] = tmp                   # restore: free this cell for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

The restore step is what separates this from flood-fill. Without it, a cell visited on one failed path stays marked and blocks a valid path starting elsewhere.

Mark before recursing, restore immediately after returning. The code before and after the recursive call should look like exact inverses of each other. If you squint and the two lines don't mirror each other, something is wrong.

BFS or DFS?

Minimum steps, fewest moves, shortest path in an unweighted graph? BFS. It processes nodes level by level and guarantees the first time it reaches a node is via the shortest route. DFS finds a path. Not necessarily the shortest one. See BFS vs DFS: One Question Decides It Every Time for the full decision framework.

Everything else: components, cycles, subtree properties, topological order, all paths, backtracking. DFS.

One practical note: Python's default recursion limit is 1,000. A 300x300 grid can produce a DFS chain 90,000 deep. In interviews, mention you'd convert to iterative DFS for large inputs, using an explicit stack. The logic is identical. The call stack just lives on the heap instead, with a much bigger budget.

The Quick Recap

• Tree or grid, no minimum requirement: DFS.
• Count connected regions: outer loop, DFS flood-fill inside.
• Cycle in directed graph: three-color DFS, not boolean visited.
• Subtree computation (height, sum, diameter): postorder DFS.
• Answer forks but parent only sees one branch: return one value, track global separately.
• All paths or grid backtrack: DFS with mark-and-restore.
• Minimum steps: BFS, not DFS.

Recognizing these signals under time pressure is easier when you've said the reasoning aloud before. SpaceComplexity runs voice-based mock interviews where an AI interviewer listens as you walk through exactly this kind of pattern identification, then scores your communication and reasoning on a rubric.

For the mechanics of what DFS is actually doing at the call-stack level, see Depth-First Search: The Algorithm Behind Half Your Graph Problems. For cycle detection in the context of ordering problems, Topological Sort: Dependencies Have an Order walks through the directed graph case end to end.

Further Reading

• Depth-first search on Wikipedia
• DFS for a Graph on GeeksforGeeks
• Detect Cycle in Directed Graph Using Colors (GeeksforGeeks)
• LeetCode 543: Diameter of Binary Tree
• LeetCode 124: Binary Tree Maximum Path Sum