BFS is extremely useful. You may not imagine.

Here we try to compile a list of inspiring BFS problems.

Name | Comment |
---|---|

bfs: level=0 vs level=1 | |

bfs first level/normal level/last level | last level would be empty |

bfs with priority queue | |

When to collect result: before enque vs after deque | |

Understand the physical meaning of level | LeetCode: As Far from Land as Possible |

If original grid can be changed, visited bool array might be optional | LeetCode: As Far from Land as Possible |

Some BFS may not necessarily need visited hashmap: say topological BFS sort | LeetCode: Course Schedule II |

BFS traverse nodes with same value of different positions | LeetCode: Jump Game IV |

**Code Skeleton**

// Blog link: https://code.dennyzhang.com/maximum-level-sum-of-a-binary-tree // Basic Ideas: bfs // // Complexity: Time O(n), Space O(n) /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxLevelSum(root *TreeNode) int { level, maxSum, res := 1, -1<<31, 0 queue := []*TreeNode{root} for len(queue) != 0 { l := []*TreeNode{} sum := 0 for _, node := range queue { sum += node.Val if node.Left != nil { l = append(l, node.Left) } if node.Right != nil { l = append(l, node.Right) } } if sum > maxSum { maxSum, res = sum, level } queue = l level++ } return res }

- BFS in string: Letter Case Permutation
- Distance with power: Cheapest Flights Within K Stops
- Revisit seen nodes: Knight Probability in Chessboard
- BFS with heap: Movie Network
- For seen set use array, instead of a set: Is Graph Bipartite
- Scan from target to original: Reach a Number
- BFS with memoization: Target Sum

See all bfs problems: #bfs

- Review: BFS Problems
- LintCode: Social Network
- LintCode: Police Distance
- Lintcode: Movie Network
- LintCode: Maximum Association Set
- LintCode: Island City
- LintCode: Deliver The Message
- LeetCode: Word Ladder II
- LeetCode: Word Ladder
- LeetCode: Web Crawler
- LeetCode: Walls and Gates
- LeetCode: Two Sum IV – Input is a BST
- LeetCode: Tree Diameter
- LeetCode: Trapping Rain Water II
- LeetCode: The Maze III
- LeetCode: The Maze II
- LeetCode: The Maze
- LeetCode: Symmetric Tree
- LeetCode: Sliding Puzzle
- LeetCode: Similar String Groups
- LeetCode: Shortest Path with Alternating Colors
- LeetCode: Shortest Path in Binary Matrix
- LeetCode: Shortest Path in a Grid with Obstacles Elimination
- LeetCode: Shortest Distance to a Character
- LeetCode: Shortest Distance from All Buildings
- LeetCode: Shortest Bridge
- LeetCode: Serialize and Deserialize N-ary Tree
- LeetCode: Sequence Reconstruction
- LeetCode: Rotting Oranges
- LeetCode: Remove Invalid Parentheses
- LeetCode: Push Dominoes
- LeetCode: Print Binary Tree
- LeetCode: Path Sum
- LeetCode: Parallel Courses
- LeetCode: Pacific Atlantic Water Flow
- LeetCode: Output Contest Matches
- LeetCode: Out of Boundary Paths
- LeetCode: Open the Lock
- LeetCode: Numbers With Same Consecutive Differences
- LeetCode: Number of Ways of Cutting a Pizza
- LeetCode: Network Delay Time
- LeetCode: N-ary Tree Level Order Traversal
- LeetCode: Minimum Time to Collect All Apples in a Tree
- LeetCode: Minimum Moves to Move a Box to Their Target Location
- LeetCode: Minimum Knight Moves
- LeetCode: Minimum Height Trees
- LeetCode: Minimum Genetic Mutation
- LeetCode: Maximum Score Words Formed by Letters
- LeetCode: Maximum Level Sum of a Binary Tree
- LeetCode: Maximum Depth of N-ary Tree
- LeetCode: Matrix Cells in Distance Order
- LeetCode: Letter Case Permutation
- LeetCode: Knight Probability in Chessboard
- LeetCode: Knight Dialer
- LeetCode: Kill Process
- LeetCode: Keys and Rooms
- LeetCode: Jump Game IV
- LeetCode: Jump Game III
- LeetCode: Is Graph Bipartite?
- LeetCode: Graph Valid Tree
- LeetCode: Generalized Abbreviation
- LeetCode: Frog Jump
- LeetCode: Find the Kth Smallest Sum of a Matrix With Sorted Rows
- LeetCode: Find Leaves of Binary Tree
- LeetCode: Find Bottom Left Tree Value
- LeetCode: Escape a Large Maze
- LeetCode: Employee Importance
- LeetCode: Directed Graph Loop
- LeetCode: Diagonal Traverse II
- LeetCode: Cousins in Binary Tree
- LeetCode: Course Schedule II
- LeetCode: Course Schedule
- LeetCode: Coin Change
- LeetCode: Closest Leaf in a Binary Tree
- LeetCode: Cheapest Flights Within K Stops
- LeetCode: Champagne Tower
- LeetCode: Bus Routes
- LeetCode: Binary Tree Zigzag Level Order Traversal
- LeetCode: Binary Tree Right Side View
- LeetCode: Binary Tree Level Order Traversal II
- LeetCode: Binary Tree Level Order Traversal
- LeetCode: Average of Levels in Binary Tree
- LeetCode: All Paths from Source Lead to Destination
- LeetCode: All Nodes Distance K in Binary Tree
- LeetCode: 01 Matrix

See more blog posts.