BFS and DFS Interview Questions
How do BFS and DFS differ, and when do you use each? — spoken sample answer for Indian interviews.
- 5Questions with answers
- 3Difficulty levels
Questions (5)
Browse beginner, intermediate, and advanced questions with answers — hide them when you want to self-test.
How do BFS and DFS differ, and when do you use each?
Choose between breadth-first and depth-first traversal on a graph or tree.
BFS: Explores level by level using a queue. Use for shortest path in unweighted graphs, level-order traversal, minimum moves on a grid.
DFS: Goes deep first using recursion or an explicit stack. Use for path existence, cycle detection, topological sort, connected components, tree recursion. Complexity: Time O(V + E) , Space O(V) for visited set
BFS can use more memory on wide graphs; deep DFS can overflow the call stack — switch to iterative DFS when needed. Always mark visited to avoid infinite loops on cycles.
How do you detect a cycle in a directed graph versus an undirected graph?
Undirected: DFS or BFS, skip the parent, if I see a visited neighbor that is not the parent, there is a cycle. Directed: I need recursion-stack color or a visiting state. White-grey-black: if I see grey, I found a back edge. Visited-only is not enough in directed graphs because a finished node can still be reached from elsewhere without a cycle. I would say this out loud. Mixing the two is a common fail.
How do you find the shortest path in an unweighted grid?
BFS from the start, each cell a node, four or eight neighbors depending on the problem. I mark visited when I enqueue, not when I dequeue, so I do not explode the queue. Distance is parent hops. I cannot use DFS for shortest path in an unweighted graph — DFS can find a long path first. If weights are positive and not all one, I switch to Dijkstra. If they add a wall-breaking k, that becomes BFS on a state (r, c, remaining).
When would DFS blow the stack, and what do you do?
A linked-list shaped graph of 100,000 nodes will blow default recursion in Python and can in Java. I switch to an explicit stack. I also mark visited before pushing neighbors. In interviews I mention recursion limits even if n is 20 in the prompt, because they often raise n in follow-ups. BFS can blow heap on a very wide frontier instead. I pick based on shape: deep versus wide.
How do you count connected components in an undirected graph?
I walk every node. If it is unvisited I start a DFS or BFS and increment the count. Time O(V plus E) . On a grid of 1s this is number of islands. I would not use Union-Find unless they want dynamic unions or I already have it in muscle memory. Interview default is DFS flood fill. I mention I must mark visited or I infinite-loop.
Practice with AI mock interviews
Run DSA mock interviews with AI follow-ups, instant feedback, and analytics on AiLx.
Free to start · No credit card required