When should I use DFS versus BFS in an interview?

Use BFS when the problem asks for shortest path in an unweighted graph, minimum number of steps, or level-by-level processing. BFS explores nodes in order of their distance from the source, so it naturally finds the shortest path. Use DFS when exploring all possible paths, detecting cycles, finding connected components, performing topological sort, or solving maze and path-existence problems. DFS uses less memory for deep sparse graphs; BFS uses less memory for wide shallow graphs.

What is the time and space complexity of DFS and BFS?

Both DFS and BFS have O(V + E) time complexity where V is the number of vertices and E is the number of edges, because each vertex and edge is visited at most once. Space complexity: BFS uses O(W) space where W is the maximum width of the graph (worst case O(V)). DFS uses O(D) space where D is the maximum depth (worst case O(V) for a path graph). For trees, BFS space is proportional to the widest level; DFS space is proportional to the height.

What are the most common DFS and BFS problem categories in FAANG interviews?

Based on real interview reports in LeakCode's database, the most reported categories are: number of islands and connected grid regions, shortest path and word ladder BFS problems, binary tree level order and zigzag traversal, topological sort for course scheduling, clone graph, all paths from source to target, and cycle detection in directed graphs. Grid BFS shortest path problems are the most reported single category across all companies.

How do I implement BFS for shortest path correctly?

Initialize a queue with the starting node and a visited set containing the starting node. At each level, dequeue all nodes at the current distance, and for each, enqueue unvisited neighbors (adding them to the visited set immediately to prevent re-queueing). Increment the distance counter after processing each level. Return the distance when the target is first dequeued. The common mistake is adding neighbors to the visited set only when dequeuing rather than when enqueuing, which causes multiple enqueues of the same node.

How does LeakCode help with DFS and BFS prep?

LeakCode aggregates 51,000+ real interview questions from companies including Google, Meta, Amazon, and Microsoft. You can filter DFS and BFS questions by company to see which specific traversal problem types each company asks most frequently. Google leans toward harder graph path and topological sort problems. Amazon frequently asks grid BFS and island counting variants. LeakCode makes this company-level distribution visible so you can prioritize effectively.

DFS and BFS Interview Questions: Complete Guide (2026)

Which DFS and BFS patterns appear in FAANG coding rounds, how to choose between them, and what the data from LeakCode's 51,000+ real interview reports shows about company-specific frequency.

Why DFS and BFS dominate graph interview questions

Depth-first search and breadth-first search are the two fundamental graph traversal algorithms. Together, they underpin a large fraction of all coding interview questions involving graphs, trees, grids, and state machines. Understanding when to apply each, how to implement each cleanly with proper visited tracking, and how to adapt each for specific problem variants is expected at every level from new graduate to staff engineer.

In LeakCode's database of 51,000+ real interview reports, DFS and BFS combined represent one of the highest-volume categories of coding questions. Grid-based variants (number of islands, rotting oranges, walls and gates) alone account for a substantial fraction of reported questions at Amazon, Meta, and Google.

The distinguishing factor in interviews is not whether candidates know DFS and BFS exist, but whether they can quickly identify which is appropriate for a given problem and implement it cleanly without common bugs like infinite loops from missing visited state.

Main DFS and BFS problem categories

Grid traversal and island problems

Count connected regions of identical cells in a 2D grid, find the largest region, or determine if one region can reach another. DFS is simplest for connectivity and counting. BFS is needed when problems ask for shortest path through the grid. These problems test 4-directional (and sometimes 8-directional) traversal, boundary checking, and visited state management. The most reported DFS category in LeakCode's data across all companies.

Shortest path in unweighted graphs

BFS guarantees the shortest path in unweighted graphs because it explores nodes level by level. Classic problem forms: word ladder (transform one word to another by changing one letter), shortest path in a maze, minimum steps to reach a target. Multi-source BFS (initialize the queue with all sources simultaneously) is a common optimization for problems with multiple starting points like rotting oranges or walls and gates.

Topological sort

Order tasks or nodes in a directed acyclic graph such that every node comes before its dependencies. Two approaches: DFS post-order (add each node to result after all its successors are processed, then reverse) and Kahn's BFS algorithm (repeatedly remove nodes with in-degree zero). Kahn's also detects cycles. Appears in course schedule problems, build system dependency ordering, and task management rounds at Amazon and Google.

Binary tree level order traversal

BFS on a binary tree produces nodes level by level. Variations include zigzag level order, right side view, maximum width, and level averages. BFS using a queue with level-size tracking is the standard approach. These appear in tree-focused phone screens and onsite rounds at virtually every company in LeakCode's database.

Cycle detection and path finding

Detect cycles in directed or undirected graphs. For directed graphs, DFS with a three-state coloring (unvisited, in-stack, done) detects back edges that indicate cycles. For undirected graphs, DFS with parent tracking or union-find detects redundant edges. All paths from source to target in a DAG or general graph uses DFS with path accumulation and backtracking.

Key implementation details that matter in interviews

Both DFS and BFS require a visited mechanism to prevent infinite loops in graphs with cycles. For BFS, add nodes to the visited set when they are enqueued, not when dequeued. This prevents multiple enqueues of the same node and is the most common BFS bug. For DFS on directed graphs, use a color array or in-stack boolean to distinguish currently-being-explored from fully-explored nodes.

1.Choose based on what the problem optimizes. Shortest path or minimum steps: BFS. All paths, connectivity, or ordering: DFS. If either works, choose the one that is simpler to implement for the specific problem shape.
2.State your visited mechanism. Set for general graphs, in-place marking for grids. Explicit parent-tracking for shortest path reconstruction. Describe your choice before coding.
3.Handle iterative DFS when recursion depth is an issue. Python recursion limit is 1000 by default. For large grid problems, an iterative DFS using an explicit stack avoids stack overflow errors. Mention this proactively for large-input problems.

Companies that ask DFS and BFS questions

Browse real DFS and BFS interview questions from these companies on LeakCode:

Google Meta Amazon Microsoft Uber Apple Airbnb LinkedIn

Search DFS and BFS on LeakCode

LeakCode has 51,000+ real interview questions from 2,000+ companies. Filter by company to see exactly which DFS and BFS patterns your target company asks most often.

Browse DFS and BFS Questions

How LeakCode helps with DFS and BFS prep

LeakCode indexes real candidate-reported questions from 1Point3Acres, Blind, LeetCode Discuss, Glassdoor, and Reddit. You can filter by company and see exactly which graph traversal patterns appear in recent interview cycles. This ensures you spend prep time on the variants your target company actually asks.