BFS vs DFS
Quick Answer
Use BFS when you need the shortest path in an unweighted graph, level-order traversal, or anything that requires processing nodes layer by layer. Use DFS when you need exhaustive search, path detection, cycle detection, topological sort, or backtracking.
Side-by-Side Comparison
| Aspect | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack / recursion (LIFO) |
| Traversal order | Level by level (breadth-first) | As deep as possible first (depth-first) |
| Space complexity | O(w) where w = max width of the level | O(h) where h = height/depth |
| Shortest path? | Yes (unweighted graphs) | No (finds a path, not necessarily shortest) |
| When optimal | Target is close to the root / start | Target is deep or solution needs full paths |
| Time complexity | O(V + E) | O(V + E) |
| Implementation | Iterative (queue-based loop) | Recursive or iterative (explicit stack) |
When to Use BFS
- -Shortest path in an unweighted graph or grid (maze solving, word ladder, min moves).
- -Level-order traversal of a tree (zigzag, right side view, average of levels).
- -Multi-source BFS — when starting from multiple nodes simultaneously (rotten oranges, nearest 0).
- -You need to find the minimum distance or minimum steps to reach a target.
When to Use DFS
- -Exhaustive search — enumerate all paths, combinations, permutations (backtracking).
- -Cycle detection in directed or undirected graphs.
- -Topological sort (using post-order DFS on a DAG).
- -Connected components — flood fill, number of islands, counting regions.
- -Tree problems that need full root-to-leaf paths or bottom-up aggregation (diameter, max path sum).
Key Differences
Memory usage
BFS can use significantly more memory on wide graphs because the queue holds the entire frontier (up to the width of the widest level). DFS only stores the current path, so it uses O(h) space. For balanced trees, BFS uses O(n/2) while DFS uses O(log n).
Completeness
BFS is complete — it will always find the solution if one exists (and the shortest one at that). DFS can get stuck in infinite branches in graphs with cycles unless you track visited nodes.
Trees vs Graphs
For trees, the choice depends on whether you need level-order processing (BFS) or root-to-leaf paths (DFS). For graphs, the deciding factor is usually whether you need shortest path (BFS) or need to explore every possibility (DFS).
How to Decide
- Does the problem ask for "shortest", "minimum steps", or "fewest moves"? Use BFS.
- Does the problem ask for "all paths", "all combinations", or "exists a path"? Use DFS.
- Is it a tree level-order problem (zigzag, right view)? Use BFS.
- Do you need to process nodes bottom-up or compute subtree properties? Use DFS.
- Is the graph very wide but shallow? Consider DFS to save memory.
- Is the graph very deep but narrow? Consider BFS to save memory and avoid stack overflow.
Example Problems
BFS
- 1.Binary Tree Level Order Traversal — Process each level as a group using a queue.
- 2.Word Ladder — Find the shortest transformation sequence from one word to another, changing one letter at a time.
- 3.Rotting Oranges — Multi-source BFS from all rotten oranges simultaneously to find the minimum time.
DFS
- 1.Number of Islands — Flood fill: for each unvisited land cell, DFS to mark the entire connected island.
- 2.Path Sum II — Find all root-to-leaf paths that sum to a target by building paths recursively.
- 3.Course Schedule — Detect cycles in a directed graph using DFS with three-color marking.