DFS/BFS Tree, Graph, And Grid Traversal
Asked of: Software Engineer
Last updated

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
heapqwith(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 areO(rows * cols), crawlers areO(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.
Featured in interview prep guides
Practice questions
- Build a BFS Web CrawlerAmazon · Software Engineer · Technical Screen · medium
- Solve two set and graph problemsAmazon · Software Engineer · Onsite · medium
- Find all cells reachable by downhill flowAmazon · Software Engineer · Technical Screen · easy
- Detect cycle in a directed graphAmazon · Software Engineer · Onsite · Medium
- Count regions with DFSAmazon · Software Engineer · Technical Screen · Medium
- Compute grid shortest path with obstaclesAmazon · Software Engineer · Technical Screen · Medium
- Check path in N-ary treeAmazon · Software Engineer · Onsite · Medium
- Implement DFS and tree algorithmsAmazon · Software Engineer · Technical Screen · Medium
- Implement tree left/right views via BFS and DFSAmazon · Software Engineer · Onsite · Medium
- Solve three coding tasks: binary search, tree path, subarrayAmazon · Software Engineer · Onsite · Medium
- Compute shortest path with obstaclesAmazon · Software Engineer · Technical Screen · Medium
- Find LCA in a BSTAmazon · Software Engineer · Technical Screen · Medium
Related concepts
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Shortest Path And Graph TraversalCoding & Algorithms