Coding Patterns

DFS vs BFS: What are the mental models?

DFS (Depth First Search) explores one path deeply before backtracking. BFS (Breadth First Search) explores level by level. The right choice depends on whether you need depth exploration, all paths, connected components, shortest path in unweighted graphs, or level-order traversal.

Coding PatternsDFSBFSGraphsTreesTraversal

The Short Answer

DFS means “go deep first.” It follows one path as far as possible before backtracking.

BFS means “go wide first.” It explores all nodes at the current distance before moving to the next distance.

DFS feels like exploring a maze path. BFS feels like a ripple spreading outward from a starting point.

The Core Mental Model

DFS: Go Deep

Start

Choose one neighbor

Keep going deeper

Backtrack when stuck

BFS: Go Level by Level

Distance 0: Start

Distance 1: All neighbors

Distance 2: Neighbors of neighbors

Continue outward

DFS Mental Model: The Explorer

DFS behaves like an explorer walking through a maze. Pick a path, keep walking (recursively, go deeper) until you cannot continue, then backtrack and try another path.

java

void dfs(Node node) {
    if (node == null) {
        return;
    }

    visit(node);

    for (Node neighbor : node.neighbors) {
        dfs(neighbor);
    }
}

DFS naturally fits problems where you need to explore possibilities, recurse into structure, or process a full connected region.

DFS Is Good For

Trees, recursion, backtracking, connected components, islands, and “explore everything reachable” problems.

Example Problem

Number of Islands

BFS Mental Model: The Ripple

BFS behaves like dropping a stone in water. It visits everything one step away, then everything two steps away, then three steps away.

java

Queue<Node> queue = new ArrayDeque<>();
// maintain list of visited nodes that should not be visited again
Set<Node> visited = new HashSet<>();

queue.offer(start); // add node to queue
visited.add(start); // also mark it as visited

// observe the net effect is that as you poll or pop items from the queue
// they come out in level order: A, B, C, D, E, F, G
while (!queue.isEmpty()) {
    Node node = queue.poll();
    visit(node);

    // visit its neighbors, and add them to the queue
    for (Node neighbor : node.neighbors) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.offer(neighbor);
        }
    }
}

BFS naturally fits shortest-path problems in unweighted graphs because the first time BFS reaches a node, it reached it using the fewest number of edges.

BFS Is Good For

Shortest path in unweighted graphs, level-order traversal, minimum steps, and nearest target problems.

Example Problem

Binary Tree Level Order Traversal

The Biggest Difference

Question	DFS	BFS
Data structure	Stack or recursion	Queue
Exploration style	Deep path first	Level by level
Best natural fit	Exhaustive exploration	Shortest path by number of steps
Common risk	Stack overflow on deep recursion	Queue can become large

When to Reach for DFS

Use DFS when the problem sounds like:

Explore all connected cells.
Find whether a path exists.
Traverse a tree recursively.
Generate all combinations or permutations.
Detect cycles.
Process dependencies deeply.

DFS is often the right default when the problem is about fully exploring a structure, not necessarily finding the fewest steps.

When to Reach for BFS

Use BFS when the problem sounds like:

Find the shortest path in an unweighted graph.
Find the minimum number of moves.
Process a tree level by level.
Find the nearest target.
Spread outward from multiple starting points.
Model waves, infection, rotting, or distance.

BFS is usually the right choice when the word “minimum” or “nearest” appears in an unweighted graph/grid problem.

Grid Problems: DFS vs BFS

Grid problems are where DFS and BFS become very intuitive.

DFS on a Grid

Flood-fill one region completely before returning.

BFS on a Grid

Expand outward one distance layer at a time.

java

int[][] directions = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};

The neighbor logic is often the same. The difference is whether you use recursion/stack or a queue.

The Visited Set Is Not Optional

In graphs and grids, you usually need a visited set or visited matrix.

java

if (visited.contains(node)) {
    return;
}

visited.add(node);

Without visited tracking, you can revisit the same nodes forever in graphs with cycles.

In trees, visited is often unnecessary because there are no cycles. In general graphs, visited is usually essential.

A Simple Decision Rule

Use DFS

When you need to explore all possibilities, all connected nodes, or recursive structure.

Use BFS

When you need shortest path, minimum steps, nearest target, or level-order traversal.

Problems to Cover Later

DFS / Connected Components

Number of Islands

DFS / Backtracking

Subsets

DFS / Cycle Detection

Course Schedule

DFS / Tree Recursion

Maximum Depth of Binary Tree

BFS / Level Order

Binary Tree Level Order Traversal

BFS / Minimum Steps

Rotting Oranges

BFS / Shortest Path Grid

Shortest Path in Binary Matrix

Multi-Source BFS

Walls and Gates

The Interview-Friendly Explanation

DFS explores deeply using recursion or a stack, so it is natural for recursive structure, backtracking, connected components, and exhaustive exploration. BFS explores level by level using a queue, so it is natural for shortest path in unweighted graphs, minimum steps, nearest target, and level-order traversal. In graphs, both usually need visited tracking to avoid cycles.

Common Interview Follow-Ups

Is DFS always recursive?

No. DFS can be implemented recursively or iteratively with an explicit stack.

Why does BFS find shortest paths in unweighted graphs?

Because BFS explores all nodes at distance 1 before distance 2, all nodes at distance 2 before distance 3, and so on. The first time it reaches a node is the fewest-edge path.

When do you need a visited set?

Use visited tracking for graphs or grids where cycles or repeated paths are possible. For ordinary trees, visited is often unnecessary.

Which uses more memory?

It depends. BFS can hold a large frontier in the queue. DFS can use deep recursion stack space. The structure of the graph or tree matters.

Can DFS find a shortest path?

DFS can find a path, but not necessarily the shortest one unless you search all paths or add extra logic. For unweighted shortest path, BFS is usually cleaner.

Final Takeaway

Do not memorize DFS and BFS as code snippets only. Remember the shape of exploration: DFS goes deep and backtracks. BFS spreads outward level by level. That mental picture usually tells you which one the problem wants.