← Pattern comparisons

DFS vs BFS

Both traverse graphs/trees, but they optimize for different goals.

Study Depth-First Search Study Breadth-First Search

Depth-First Search

O(V + E) time, O(h) to O(V) space (stack/recursion)

Use When

  • Need full path exploration, recursion, or subtree aggregation
  • Memory should scale by depth instead of breadth
  • Backtracking-style state is part of the solution

Avoid When

  • You must guarantee shortest path in unweighted graph
  • You need strict level-by-level processing
Mental model: Go deep, then backtrack.
VS

Breadth-First Search

O(V + E) time, O(w) to O(V) space (queue width)

Use When

  • Need shortest path / minimum steps in unweighted graph
  • Level-order processing or multi-source expansion
  • Distance from source matters directly

Avoid When

  • Graph is very wide and memory is tight
  • Only subtree/path aggregation is needed
Mental model: Expand in waves from the source.

Decision Checklist

  1. If prompt says shortest/minimum steps in unweighted graph, default to BFS.
  2. If prompt says all paths, subtree totals, or recursive structure, prefer DFS.
  3. Estimate graph width first if memory is a concern.