BFS vs DFS: When to Use Which

Feb 18, 20268 min read

Breadth-First Search (BFS) and Depth-First Search (DFS) are the two fundamental graph and tree traversal algorithms. Every software engineer needs to know both, but the real interview skill is knowing which one to pick for a given problem. This guide gives you a clear comparison, the trade-offs in space and time, and concrete problems where each one shines.

The Core Idea

BFS: Layer by Layer

BFS uses a queue. It visits all nodes at distance 1, then all nodes at distance 2, and so on. It naturally finds the shortest path in an unweighted graph because it explores closer nodes first.

DFS: Dive Deep First

DFS uses a stack (or recursion). It explores one path as deeply as possible before backtracking. It is the natural choice for exhaustive search, connected components, and tree traversals.

Comparison Table

Aspect	BFS	DFS
Data structure	Queue (FIFO)	Stack / Recursion (LIFO)
Traversal order	Level by level	Branch by branch (deep first)
Shortest path?	Yes (unweighted graphs)	No (finds a path, not necessarily shortest)
Time complexity	O(V + E)	O(V + E)
Space (tree)	O(w) — width of tree (can be O(n))	O(h) — height of tree (O(log n) for balanced)
Space (graph)	O(V)	O(V)
Best for	Shortest path, minimum steps, level-order	All paths, connected components, topological sort

When to Use BFS

BFS is the right choice whenever the problem is about finding the nearest, shortest, or minimum-cost result in an unweighted graph. It is also the go-to for level-order tree traversal.

Shortest path in unweighted graph: BFS guarantees the first time you reach a node is via the shortest path.
Minimum moves / steps: "Minimum number of moves to reach target" is BFS territory.
Level-order traversal: Process all nodes at depth d before depth d+1.
Multi-source BFS: Start BFS from multiple sources simultaneously (e.g., Rotting Oranges, 01 Matrix).
Word transformations: Word Ladder problems where each step changes one character.

BFS Code Template

function bfs(start: Node): number {
  const queue: [Node, number][] = [[start, 0]];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const [node, distance] = queue.shift()!;

    if (isTarget(node)) return distance;

    for (const neighbor of node.neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1]);
      }
    }
  }
  return -1; // not reachable
}

Example BFS Problems

Binary Tree Level Order Traversal — Process nodes level by level. BFS naturally groups nodes by depth.
Rotting Oranges — Multi-source BFS from all rotten oranges simultaneously. The number of BFS rounds equals the minimum time.
Word Ladder — Find the shortest transformation sequence from one word to another. Each word is a node; edges connect words that differ by one letter.

When to Use DFS

DFS is the right choice when you need to explore all possibilities, find all paths, or compute properties of subtrees. It uses less space than BFS on deep, narrow structures (like balanced trees) and is the backbone of backtracking.

Connected components: Flood-fill every unvisited node to count or label components (Number of Islands).
Path existence and all paths: DFS explores each branch completely, making it ideal for "does a path exist?" or "find all paths from A to B."
Tree depth and diameter: Post-order DFS computes subtree heights and diameters.
Topological sort: DFS-based topological sort uses finish times to order a DAG.
Backtracking: Permutations, combinations, Sudoku, N-Queens — all are DFS with pruning.

DFS Code Template

function dfs(node: TreeNode | null): number {
  if (!node) return 0;

  const left = dfs(node.left);
  const right = dfs(node.right);

  // post-order: process after children
  return Math.max(left, right) + 1;
}

// For graphs with cycle protection:
function dfsGraph(node: Node, visited: Set<Node>): void {
  visited.add(node);
  for (const neighbor of node.neighbors) {
    if (!visited.has(neighbor)) {
      dfsGraph(neighbor, visited);
    }
  }
}

Example DFS Problems

Number of Islands — DFS from each unvisited land cell to mark the entire island. Count the number of DFS calls.
Maximum Depth of Binary Tree — Recursive DFS returns 1 + max(left depth, right depth).
Path Sum — DFS from root to leaves, subtracting each node's value from the target. Return true if the target reaches 0 at a leaf.

Space Complexity: The Key Trade-Off

The biggest practical difference between BFS and DFS is their space usage, especially on trees:

BFS on a tree: The queue holds up to one entire level. In a balanced binary tree, the widest level has ~n/2 nodes, so BFS uses O(n) space. In a skewed tree (like a linked list), BFS uses O(1) space because each level has one node.

DFS on a tree: The call stack (or explicit stack) holds one root-to-leaf path. In a balanced binary tree, that is O(log n). In a skewed tree, it is O(n).

Rule of thumb: If the tree is wide and short, DFS uses less space. If the tree is tall and narrow, BFS uses less space. For most practical trees (balanced or near-balanced), DFS is more space-efficient.

Quick Decision Framework

Need shortest path / minimum moves? → BFS

Need level-order traversal? → BFS

Multi-source spreading (rotting oranges, fire)? → BFS

Need to explore all paths or check path existence? → DFS

Need connected components? → DFS (or BFS — both work)

Need topological ordering? → DFS (or Kahn's BFS)

Generate all permutations/combinations? → DFS (backtracking)

Tree depth, diameter, subtree properties? → DFS (post-order)

Can You Use Both?

Yes. Some problems can be solved with either BFS or DFS. Connected components, for example, work with both. However, for shortest-path problems in unweighted graphs, BFS is required — DFS will find a path but not necessarily the shortest one. And for backtracking problems, DFS is the natural fit because you need to build up partial solutions and undo them.

For more on these patterns, explore our interactive walkthroughs:

Test your graph traversal skills

Can you identify whether a problem needs BFS or DFS just from the description? Take our pattern recognition quiz.

Take the Quiz Browse All Patterns