Documentation Index
Fetch the complete documentation index at: https://swe.aboneda.com/llms.txt
Use this file to discover all available pages before exploring further.
Depth-First Search & Breadth-First Search
The two fundamental graph/tree traversal strategies that form the backbone of countless algorithms.
DFS (Depth-First Search)
Explores as far as possible along each branch before backtracking.
Approaches
- Recursive — natural and concise, uses the call stack
- Iterative — uses an explicit stack, avoids stack overflow
Time & Space
| Time | Space |
|---|
| Tree | O(n) | O(h) — height of tree |
| Graph | O(V + E) | O(V) |
Common DFS Patterns
- Pre-order, in-order, post-order traversal (trees)
- Connected components
- Cycle detection
- Path finding
- Topological sort (via post-order)
BFS (Breadth-First Search)
Explores all neighbors at the current depth before moving to the next level.
Implementation
Uses a queue (FIFO). Process nodes level by level.
Time & Space
| Time | Space |
|---|
| Tree | O(n) | O(w) — max width |
| Graph | O(V + E) | O(V) |
Common BFS Patterns
- Level-order traversal
- Shortest path in unweighted graphs
- Multi-source BFS (e.g., rotting oranges)
- BFS on implicit graphs (word ladder, puzzle states)
DFS vs BFS
| Aspect | DFS | BFS |
|---|
| Data structure | Stack | Queue |
| Shortest path | No (unweighted) | Yes (unweighted) |
| Memory | O(h) or O(V) | O(w) or O(V) |
| Best for | Exhaustive search, backtracking | Shortest path, level-order |
Classic Problems
- Number of Islands
- Clone Graph
- Word Ladder (BFS)
- Course Schedule (DFS cycle detection)
- Binary Tree Level Order Traversal (BFS)
- Pacific Atlantic Water Flow
- Surrounded Regions
- Shortest Path in Binary Matrix (BFS)
