BFS / DFS (Graph & Tree Traversal)

Breadth-first search explores level by level (shortest path in unweighted graphs); depth-first explores one branch fully before backtracking.

When to use it

Shortest path / fewest steps in an unweighted graph or grid → BFS.
Exploring all paths, connectivity, or tree structure problems → DFS.
Topological sort, cycle detection in directed graphs.

Signals in the problem statement

Graph/tree/grid input.
'Shortest'/'minimum steps' → BFS.
'All paths'/'connected components' → DFS.

Common pitfalls

Forgetting a visited set, causing infinite loops on cyclic graphs.
Using DFS for shortest-path-in-unweighted-graph problems (wrong tool — BFS guarantees shortest first).

Practice Problems

Number of Islands

Medium

Asked at: Amazon, Google, Meta

Practiced

Given a 2D grid of '1's (land) and '0's (water), count the number of islands (connected land regions, 4-directionally).

Time: O(rows * cols) · Space: O(rows * cols) worst case recursion/queue

Word Ladder (Shortest Transformation)

Hard

Asked at: Amazon, Google, LinkedIn

Practiced

Given a start word, end word, and a dictionary, find the length of the shortest transformation sequence changing one letter at a time, each intermediate word in the dictionary.

Time: O(n * L^2) where n = dictionary size, L = word length · Space: O(n * L)