BFS - rFronteddu/general_wiki GitHub Wiki
Breadth-First Search (BFS) is the go-to strategy when you need to explore a graph or tree layer by layer. Because it radiates outward from the starting point, it is the mathematically guaranteed way to find the shortest path in any unweighted graph.
Easy: The BFS Skeleton
These problems focus on the basic template: using a Queue and a while loop to process levels.
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Average of Levels in Binary Tree
- Minimum Depth of Binary Tree
- Cousins in Binary Tree
Medium: Shortest Paths & Grid Traversal
These problems often involve 2D grids (matrices) where each cell is a node and adjacent cells are edges.
- Binary Tree Zigzag Level Order Traversal
- Populating Next Right Pointers in Each Node
- Rotting Oranges
- Shortest Path in Binary Matrix
- 01 Matrix
- Clone Graph
- Word Ladder
Hard: Advanced State BFS
In these problems, "Visited" isn't just a coordinate; it's a combination of location and current status (like keys held or moves remaining).