Home / Blog / DFS vs BFS Interview Pattern Chooser

DFS vs BFS Interview Pattern Chooser

Published 2026-10-12 · Luna Interview

Graph and grid prompts often start the same way: “traverse these nodes.” The fork that wastes time is picking the wrong traversal. This DFS vs BFS interview pattern chooser gives you a 10-second decision, talk tracks, and templates so you commit early and implement cleanly.

The 10-second classification

Ask:

1. Do I need the shortest path in an unweighted graph or grid? → BFS
2. Do I need to explore paths, backtrack, or build permutations/subsets on a graph-shaped search? → DFS (often with recursion)
3. Am I flooding a region / counting connected components? → either works; pick the one you write faster
4. Is the graph huge and deep with risk of recursion limits? → prefer iterative BFS/DFS with an explicit stack

Talk track:

“If we need shortest path in unweighted edges, I’ll BFS by layers. If we need path exploration or backtracking, I’ll DFS. For connected components, I’ll pick DFS unless the interviewer prefers BFS.”

When BFS is the right default

Template sketch (grid):

from collections import deque

def bfs(grid, start):
    q = deque([start])
    seen = {start}
    dist = {start: 0}
    while q:
        r, c = q.popleft()
        for nr, nc in neighbors(r, c):
            if (nr, nc) in seen or not valid(nr, nc):
                continue
            seen.add((nr, nc))
            dist[(nr, nc)] = dist[(r, c)] + 1
            q.append((nr, nc))
    return dist

Say out loud: “Queue + visited; distance is parent + 1.”

When DFS is the right default

Template sketch:

def dfs(node, seen):
    if node in seen:
        return
    seen.add(node)
    for nxt in graph[node]:
        dfs(nxt, seen)

For path-building, remove from seen when backtracking is required (or use a path set separate from permanent visited—state which one you mean).

Side-by-side chooser

Failure modes that burn the clock

1. BFS without visited → infinite loops on cycles
2. DFS recursion on deep graphs → stack overflow; switch to iterative
3. Using DFS for unweighted shortest path → wrong distances unless you carefully track best cost
4. Marking visited too late → same node queued many times (BFS) or exponential blowups
5. Confusing path-visited with global-visited in backtracking

Talk track when correcting yourself:

“I used DFS, but we need minimum steps—I’ll switch to BFS so the first hit is shortest.”

Complexity sentences to keep ready

• BFS/DFS adjacency list: O(V + E) time; O(V) space for visited (+ queue/stack)
• Grid: O(R·C) if each cell processed once
• Backtracking DFS: often exponential; say the branching factor honestly

Practice plan

Iterative DFS when recursion is risky

Deep graphs or constrained pad stacks argue for an explicit stack:

def iterative_dfs(start, graph):
    stack = [start]
    seen = {start}
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return seen

Talk track:

“Same DFS order family, but the stack is explicit so we control memory and avoid recursion limits.”

0-1 BFS and weighted edges (know the boundary)

Plain BFS is wrong for arbitrary positive weights—that is Dijkstra. If edge weights are only 0 or 1, a deque 0-1 BFS is a fair follow-up. Mention it only if the prompt has weights; do not force it.

Grid neighbor hygiene

Always state neighbor order and bounds checks. A one-liner helps:

“Four-directional moves, skip out-of-bounds and blocked cells, mark visited when enqueueing for BFS.”

Marking on enqueue (BFS) vs on pop are both discussable; be consistent and avoid duplicate queue growth.

Soft practice note

Traversal mistakes are usually classification mistakes. If you want a side panel to rehearse the DFS vs BFS talk track under a timer, Luna Interview is built for calm structured practice—not for anything that violates interview rules.

Day-of checklist

• [ ] Shortest unweighted? → BFS
• [ ] Backtracking / path build? → DFS
• [ ] Visited policy stated
• [ ] Queue vs recursion chosen deliberately
• [ ] Complexity spoken
• [ ] Tiny example dry-run

Choose the traversal for the question you are answering—not the one you practiced last night.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.