BFS / DFS: when to spot it, explain it, and practice it
BFS and DFS are less about memorizing traversal syntax and more about knowing whether you are exploring exhaustively, detecting structure, or searching for the shortest layered answer.
Pattern coverage
80+
Best first move
Decide whether the problem needs breadth, depth, or both.
Common failure point
Marking visited too late and enqueuing duplicates.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Identify the graph model and how neighbors are generated.
Choose BFS for shortest unweighted distance or DFS for structure exploration.
Maintain visited consistently so the same state is not processed twice.
Track the extra state that the answer depends on, such as level or path sum.
Handle disconnected components if the traversal can start from multiple places.
Common variants
Grid traversal
Great for flood fill, island counting, and boundary propagation.
Tree traversal
Useful when parent-child structure and path information matter.
State-space search
Useful when each node is a state, such as word ladder or lock rotation.
Template preview
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
def dfs(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(nxt)
Classic problems with useful framing
#200
Number of Islands
The canonical grid traversal starter.
Count the number of islands in a grid.
#102
Binary Tree Level Order Traversal
Best first example for BFS by levels.
Return the level-order traversal of a binary tree.
#207
Course Schedule
Bridges traversal with DAG reasoning.
Determine whether all courses can be finished given prerequisites.
#127
Word Ladder
A true shortest-path BFS interview classic.
Find the shortest transformation sequence from beginWord to endWord.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#98 Validate Binary Search Tree
Check whether a binary tree is a valid BST.
Each subtree inherits a value range from its ancestors, and every node must stay strictly inside that range.
Foundation
#102 Binary Tree Level Order Traversal
Return the level-order traversal of a binary tree.
One queue layer equals one answer layer, so you should snapshot the queue size before processing the current level.
Variant depth
#200 Number of Islands
Count the number of islands in a grid.
Once you discover one land cell, the whole connected component should be consumed in one traversal.
Variant depth
#207 Course Schedule
Determine whether all courses can be finished given prerequisites.
The answer is no exactly when the directed graph contains a cycle.
Pressure test
#127 Word Ladder
Find the shortest transformation sequence from beginWord to endWord.
The hard part is not BFS itself but generating neighbors efficiently without trying every word naively.
High-frequency mistakes
Marking visited too late and enqueuing duplicates.
Using recursive DFS where depth can overflow the stack.
Mixing path-specific state with global visited state incorrectly.
Forgetting to scan all components when the graph is disconnected.
Recommended practice path
Start with grid DFS and island problems.
Then solve tree traversal questions and simple graph cloning.
After that, move to topological sort and cycle detection.
Finish with harder state-space BFS questions such as word ladder.