DFS/BFS Tree, Graph, And Grid Traversal

What's being tested

Graph traversal skill across trees, grids, and network-like graphs: choosing DFS, BFS, or Dijkstra based on reachability, shortest unweighted distance, or weighted cost. Interviewers probe whether you maintain correct state, avoid revisits, handle branching/obstacles/errors, and explain time/space complexity clearly.

Patterns & templates

• BFS shortest path on unweighted graphs — use queue, visited, and level counting; O(V + E) time, O(V) space.

• Multi-source BFS for spreading processes — enqueue all initial rotten/spoiled cells first; each BFS layer represents one time unit.

• DFS path matching in an N-ary tree — recurse with (node, index) state; backtracking is implicit, and duplicate values require sequence-position tracking.

• Grid traversal template — iterate four directions via dirs = [(1,0),(-1,0),(0,1),(0,-1)]; validate bounds, obstacles, and visited cells.

• Dijkstra-style traversal for weighted cells — use heapq with (cost, r, c); mark finalized distances, not merely first-seen nodes.

• Web crawler BFS — normalize URLs, enforce same-domain scope, dedupe with visited, and separate fetch failures/retries from traversal correctness.

• Complexity framing — trees are O(n), grids are O(rows * cols), crawlers are O(pages + links) bounded by crawl limit and dedupe set.

Common pitfalls

Pitfall: Using DFS for shortest path in an unweighted grid without tracking all alternatives; BFS is the canonical shortest-step solution.

Pitfall: Marking weighted grid nodes visited when pushed into the heap; with Dijkstra, finalize when popped with the minimum known distance.

Pitfall: Matching N-ary tree paths by value only; repeated values mean your state must include the current sequence index.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.