When do you use BFS versus DFS on a graph?
Reported in Deloitte interview loops. Graph traversal question covering shortest paths, connectivity, and complexity.
Interview scenario
Often asked in Deloitte technical or coding rounds. Prepare a clear spoken answer plus key trade-offs.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Deloitte: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
BFS explores level by level using a queue. It finds shortest paths in unweighted graphs and is ideal for minimum hops, broadcast, and nearest-neighbor problems. Time O(V + E), space O(V) for queue and visited set.
DFS dives deep along one path before backtracking, typically with recursion or an explicit stack. Use it for cycle detection, topological sort, connected components, path existence, and maze exploration where shortest path is not required.
On trees: BFS suits level-order traversal; DFS (pre/in/post-order) suits subtree aggregation and path sums. On large graphs, DFS recursion depth may overflow—prefer iterative DFS or BFS.
Always state representation (adjacency list vs matrix), visited tracking, and handling directed vs undirected edges. Mention bidirectional BFS for faster shortest path in large sparse graphs.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.