What is the difference between BFS (Breadth-First Search) and DFS (Depth-First Search) and their space-time complexities?
Quick Revision Summary
BFS uses a Queue and finds shortest unweighted paths. DFS uses a Stack/recursion and is ideal for topological sort and cycle detection.
Interactive Practice Mode
Formulate your thoughts or take notes before revealing the model solution.
Saved automatically
Model Answer & Deep-Dive Explanation
Breadth-First Search (BFS): Traverses graph level-by-level using a Queue (FIFO). It explores all direct neighbors at depth $d$ before moving to depth $d+1$.
- Use cases: Finding shortest path in unweighted graphs, finding closest peer nodes.
- Complexity: Time $O(V + E)$, Space $O(V)$ (stores maximum width of the graph).
Depth-First Search (DFS): Traverses graph branch-by-branch using a Stack (LIFO) or recursion. It explores as deep as possible along each branch before backtracking.
- Use cases: Topological sorting, cycle detection, maze solving, connected components.
- Complexity: Time $O(V + E)$, Space $O(h)$ where $h$ is maximum tree/graph recursion depth.
Interviewer Evaluation Points & Scoring Rubric
- 1 1. Distinguishes Queue vs Stack. 2. States O(V + E) time. 3. Connects BFS to shortest path and DFS to cycle detection.
Related Questions in Data Structures & Algorithms
How to detect a cycle in a Linked List using Floyd's Cycle-Finding Algorithm?
Intermediate level • 513 views
Explain the LRU (Least Recently Used) Cache architecture and how to implement it in O(1) time complexity.
Advanced level • 1 views
How do you design a Distributed API Rate Limiter and what algorithms are commonly employed?
Advanced level • 1 views
What is Dynamic Programming? Compare Memoization (Top-Down) with Tabulation (Bottom-Up) using the 0/1 Knapsack Problem.
Advanced level • 1 views
When would you choose a hash map instead of an array for lookups?
Easy level • 1 views