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 |

**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: Frog Jump
- LintCode: Deliver The Message
- Leetcode: Word Ladder II
- Leetcode: Word Ladder
- Leetcode: Web Crawler
- Leetcode: Walls and Gates
- Leetcode: Trapping Rain Water II
- Leetcode: The Maze II
- Leetcode: The Maze
- Leetcode: Target Sum
- Leetcode: Swim in Rising Water
- Leetcode: Sliding Puzzle
- Leetcode: Similar String Groups
- Leetcode: Shortest Path with Alternating Colors
- Leetcode: Shortest Path in Binary Matrix
- Leetcode: Shortest Distance to a Character
- Leetcode: Shortest Bridge
- 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: Network Delay Time
- Leetcode: N-ary Tree Level Order Traversal
- Leetcode: Minimum Knight Moves
- Leetcode: Minimum Height Trees
- Leetcode: Minimum Genetic Mutation
- Leetcode: Minesweeper
- 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: Keys and Rooms
- Leetcode: Is Graph Bipartite?
- Leetcode: Graph Valid Tree
- Leetcode: Generalized Abbreviation
- Leetcode: Find Bottom Left Tree Value
- Leetcode: Escape a Large Maze
- Leetcode: Employee Importance
- Leetcode: Directed Graph Loop
- 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.