Breadth-First Search Coding Problems: 156 Questions with Solutions
156 breadth-first search coding problems — 19 easy · 95 medium · 42 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 156
- By difficulty: 19 easy · 95 medium · 42 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Breadth-first search explores a graph or grid one layer at a time from a start, so the first time it reaches a node is along a shortest path in edges. Shortest paths in an unweighted maze, level-order traversal, the minimum number of moves, and "rotting oranges"-style spreading processes are all BFS with a queue and a visited set; these problems practise setting that up cleanly.
New to breadth-first search? Read the Breadth-First Search (BFS) tutorial first.
How breadth-first search works, step by step
edges = A–B, A–C, B–D, C–D, C–E, D–F, E–F, F–G; start = A- Start at A: its distance is 0, it is marked as seen, and it is the only node in the queue. The queue is what keeps the search in order of distance.
- Take A off the front (distance 0). Its unseen neighbours B and C are marked at distance 1 and joined the back of the queue.
- Take B off the front (distance 1). Its unseen neighbour D is marked at distance 2 and joined the back of the queue; A was already seen and is skipped.
- Take C off the front (distance 1). Its unseen neighbour E is marked at distance 2 and joined the back of the queue; A and D were already seen and are skipped.
- Take D off the front (distance 2). Its unseen neighbour F is marked at distance 3 and joined the back of the queue; B and C were already seen and are skipped.
- Take E off the front (distance 2). Every neighbour (C and F) is already marked, so nothing is added.
- Take F off the front (distance 3). Its unseen neighbour G is marked at distance 4 and joined the back of the queue; D and E were already seen and are skipped.
- Take G off the front (distance 4). Every neighbour (F) is already marked, so nothing is added.
- The queue is empty and every node has its shortest distance from A in edges — G is the farthest at 4. The marked edges are the BFS tree: following them back from any node gives a shortest path. Each node and edge was handled once: O(V + E).
Breadth-First Search study plan
14 of the 156 Breadth-First Search problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 142 in the full list below are practice at your own pace. Then move on to Depth-First Search.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
- Flood Fill Easy
- Find if Path Exists in Graph Easy
- Same Tree Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Symmetric Tree Easy
- Number of Islands Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Rotting Oranges Medium
- Keys and Rooms Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Pacific Atlantic Water Flow Medium
- Surrounded Regions Medium
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Word Ladder Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Swim in Rising Water Hard
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Breadth-First Search: the essentials
When to reach for it
"The minimum number of moves, steps or transformations" where every move costs the same; something spreading from several sources at once (fire, infection, the distance to the nearest exit); and nodes that are generated rather than given — words one letter apart, lock combinations, board states. Once edges carry different weights, BFS stops giving shortest paths: use Dijkstra's algorithm, or a deque-based 0-1 BFS when the weights are only 0 and 1.
The pattern
Put the start, or every source, in a queue and mark it seen. Pop a node and push each unseen neighbour, marking it the moment it is pushed. Distances fall out of the order: everything at distance d leaves the queue before anything at d + 1. Graphs given as edges need an adjacency list first — see Graph.
from collections import deque
def bfs(start, neighbours):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in neighbours(node):
if nxt not in dist: # mark on push, not on pop
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
Cost
O(V + E) time and O(V) space; on an m × n grid with four moves per cell, O(m × n).
Common mistakes
- Marking a node when it is popped instead of when it is pushed, so it enters the queue many times.
- Using
list.pop(0)in Python orshift()in JavaScript as the dequeue, which can cost O(n) per pop; use adequeor a head index. - Running a multi-source problem once per source instead of seeding the queue with all of them.
- Counting the start as step 1 instead of step 0.
Start with
- Flood Fill: reachability on a grid.
- Rotting Oranges: many sources, counted in layers.
- Shortest Path in Binary Matrix: fewest moves with eight directions.
All breadth-first search problems
Easy (19)
- Level of a Node in Binary Tree Tree, Depth-First Search
- Sum of Leaf Nodes at Minimum Level Tree
- Nodes at Odd Levels Tree
- Nodes at Distance K from Root Tree, Depth-First Search
- Check if All Leaves are at Same Level Tree, Depth-First Search
- Left View of Binary Tree Tree, Depth-First Search
- Cousins in Binary Tree Tree, Depth-First Search
- Univalued Binary Tree Tree, Depth-First Search
- Merge Two Binary Trees Tree, Depth-First Search
- Minimum Absolute Difference in BST Tree, Depth-First Search
- Sum of Left Leaves Tree, Depth-First Search
- Invert Binary Tree Tree, Depth-First Search
- Path Sum Tree, Depth-First Search
- Minimum Depth of Binary Tree Tree, Depth-First Search
- Maximum Depth of Binary Tree Tree, Depth-First Search
- Symmetric Tree Tree, Depth-First Search
- Same Tree Tree, Depth-First Search
- Find if Path Exists in Graph Graph, Union Find
- Flood Fill Array, Matrix, Depth-First Search
Medium (95)
- Operations on Tree Array, Hash Table, Tree
- Bottom View of Binary Tree Tree, Hash Table
- Top View of Binary Tree Tree, Hash Table
- Cousins in Binary Tree II Tree, Hash Table
- Kth Largest Sum in a Binary Tree Tree, Sorting, Heap (Priority Queue)
- Minimum Number of Operations to Sort a Binary Tree by Level Tree, Sorting
- Reverse Odd Levels of Binary Tree Tree, Depth-First Search
- Amount of Time for Binary Tree to Be Infected Tree, Depth-First Search
- Even Odd Tree Tree
- Count Good Nodes in Binary Tree Tree, Depth-First Search
- Sum of Nodes with Even-Valued Grandparent Tree, Depth-First Search
- Deepest Leaves Sum Tree, Depth-First Search
- Maximum Level Sum of a Binary Tree Tree
- Check Completeness of a Binary Tree Tree
- Smallest Subtree with all the Deepest Nodes Hash Table, Tree, Depth-First Search
- All Nodes Distance K in Binary Tree Hash Table, Tree, Depth-First Search
- Maximum Width of Binary Tree Tree, Depth-First Search
- Add One Row to Tree Tree, Depth-First Search
- Find Largest Value in Each Tree Row Tree, Depth-First Search
- Find Bottom Left Tree Value Tree, Depth-First Search
- Binary Tree Right Side View Tree, Depth-First Search
- Binary Tree Level Order Traversal II Tree
- Binary Tree Zigzag Level Order Traversal Tree
- Binary Tree Level Order Traversal Tree
- Power Grid Maintenance Array, Hash Table, Depth-First Search
- Count Islands With Total Value Divisible by K Array, Depth-First Search, Union Find
- Unit Conversion I Depth-First Search, Graph
- Maximize the Number of Target Nodes After Connecting Trees I Tree, Depth-First Search
- Remove Methods From Project Depth-First Search, Graph
- Find a Safe Walk Through a Grid Array, Graph, Heap (Priority Queue)
- Shortest Distance After Road Addition Queries I Array, Graph
- Disconnect Path in a Binary Matrix by at Most One Flip Array, Dynamic Programming, Depth-First Search
- K Highest Ranked Items Within a Price Range Array, Sorting, Heap (Priority Queue)
- Minimum Operations to Convert Number Array
- Lexicographically Smallest String After Applying Operations String, Depth-First Search, Enumeration
- Validate Binary Tree Nodes Tree, Depth-First Search, Union Find
- Coloring A Border Array, Depth-First Search, Matrix
- Knight Walk Matrix
- Numbers With Same Consecutive Differences Backtracking
- Minesweeper Array, Depth-First Search, Matrix
- Minimum Jumps to Reach Home Array, Dynamic Programming
- All Ancestors of a Node in a Directed Acyclic Graph Graph, Depth-First Search, Topological Sort
- The Time When the Network Becomes Idle Array, Graph
- Nearest Exit from Entrance in Maze Array, Matrix
- Check if There is a Valid Path in a Grid Matrix, Depth-First Search, Union Find
- Water and Jug Problem Math, Depth-First Search
- Bulb Switcher II Math, Bit Manipulation
- Find the Safest Path in a Grid Array, Matrix, Binary Search
- Course Schedule IV Graph, Topological Sort, Depth-First Search
- Parallel Courses Graph, Topological Sort
- Detonate the Maximum Bombs Array, Math, Graph
- The Maze II Array, Matrix, Graph
- Open the Lock Array, String
- Shortest Path with Alternating Colors Graph
- Number of Nodes in the Sub-Tree With the Same Label Hash Table, Tree, Graph
- Minimum Fuel Cost to Report to the Capital Tree, Graph, Depth-First Search
- Count the Number of Complete Components Graph, Union Find, Depth-First Search
- Minimum Score of a Path Between Two Cities Graph, Union Find, Depth-First Search
- Reachable Nodes With Restrictions Array, Tree, Graph
- Maximum Number of Fish in a Grid Array, Matrix, Depth-First Search
- Maximum Number of Moves in a Grid Array, Matrix, Dynamic Programming
- Map of Highest Peak Array, Matrix
- Find All Groups of Farmland Array, Matrix, Depth-First Search
- Pacific Atlantic Water Flow Array, Depth-First Search, Matrix
- Snakes and Ladders Array, Matrix
- Minimum Genetic Mutation Hash Table, String
- Jump Game III Array, Depth-First Search
- Count Unreachable Pairs of Nodes in an Undirected Graph Depth-First Search, Union Find, Graph
- Path With Minimum Effort Array, Binary Search, Depth-First Search
- Time Needed to Inform All Employees Tree, Depth-First Search
- Reorder Routes to Make All Paths Lead to the City Zero Depth-First Search, Graph
- Possible Bipartition Depth-First Search, Union Find, Graph
- Minimum Height Trees Depth-First Search, Graph, Topological Sort
- Detect Cycles in 2D Grid Array, Depth-First Search, Union Find
- Number of Distinct Islands Array, Hash Table, Depth-First Search
- Shortest Bridge Array, Depth-First Search, Matrix
- Number of Operations to Make Network Connected Depth-First Search, Union Find, Graph
- Count Sub Islands Array, Depth-First Search, Union Find
- As Far from Land as Possible Array, Dynamic Programming, Matrix
- Shortest Path in Binary Matrix Array, Matrix
- Number of Enclaves Array, Depth-First Search, Union Find
- Find Eventual Safe States Depth-First Search, Graph, Topological Sort
- All Paths From Source to Target Backtracking, Depth-First Search, Graph
- Keys and Rooms Depth-First Search, Graph
- Is Graph Bipartite? Depth-First Search, Union Find, Graph
- Graph Valid Tree Depth-First Search, Union Find, Graph
- Number of Connected Components in an Undirected Graph Depth-First Search, Union Find, Graph
- Perfect Squares Math, Dynamic Programming
- Count Servers that Communicate Array, Depth-First Search, Union Find
- Number of Closed Islands Array, Depth-First Search, Union Find
- Surrounded Regions Array, Depth-First Search, Union Find
- 01 Matrix Array, Matrix, Dynamic Programming
- Rotting Oranges Array, Matrix
- Number of Islands Array, Matrix, Depth-First Search
- Coin Change Array, Dynamic Programming
Hard (42)
- Height of Binary Tree After Subtree Removal Queries Tree, Depth-First Search, Array
- Vertical Order Traversal of a Binary Tree Tree, Depth-First Search, Hash Table
- Last Day Where You Can Still Cross Array, Binary Search, Depth-First Search
- Maximize the Number of Target Nodes After Connecting Trees II Tree, Depth-First Search
- Minimum Edge Reversals So Every Node Is Reachable Dynamic Programming, Depth-First Search, Graph
- Minimum Number of Visited Cells in a Grid Array, Dynamic Programming, Stack
- Minimum Reverse Operations Array, Ordered Set, Union Find
- Maximum Candies You Can Get from Boxes Array, Graph
- Minimum Number of Flips to Convert Binary Matrix to Zero Matrix Array, Hash Table, Bit Manipulation
- Minimum Moves to Move a Box to Their Target Location Array, Heap (Priority Queue), Matrix
- Escape a Large Maze Array, Hash Table, Depth-First Search
- Minimize Malware Spread II Array, Hash Table, Depth-First Search
- K-Similar Strings String
- Contain Virus Array, Depth-First Search, Matrix
- Cut Off Trees for Golf Event Array, Heap (Priority Queue), Matrix
- Freedom Trail String, Dynamic Programming, Depth-First Search
- Zuma Game String, Dynamic Programming, Memoization
- Minimum Cost to Make at Least One Valid Path in a Grid Graph, Matrix, Shortest Path
- Shortest Path in a Grid with Obstacles Elimination Array, Matrix
- Minimum Moves to Reach Target with Rotations Array, Matrix
- Shortest Path to Get All Keys Array, Bit Manipulation, Matrix
- Shortest Cycle in a Graph Graph
- Divide Nodes Into the Maximum Number of Groups Graph, Union Find
- Second Minimum Time to Reach Destination Graph, Shortest Path
- Maximum Number of Points From Grid Queries Array, Matrix, Heap (Priority Queue)
- Brace Expansion II String, Stack, Backtracking
- Remove Invalid Parentheses String, Backtracking
- Minimum Time to Visit a Cell In a Grid Array, Matrix, Graph
- Minimum Number of Days to Disconnect Island Array, Matrix, Depth-First Search
- Find All People With Secret Graph, Union Find, Depth-First Search
- Minimum Obstacle Removal to Reach Corner Array, Matrix, Graph
- Bus Routes Array, Hash Table
- Sliding Puzzle Array, Matrix
- Jump Game IV Array, Hash Table
- Trapping Rain Water II Array, Matrix, Heap (Priority Queue)
- Escape the Spreading Fire Array, Matrix, Binary Search
- Shortest Distance from All Buildings Array, Matrix
- Minimum Moves to Spread Stones Over Grid Array, Matrix, Dynamic Programming
- Making A Large Island Array, Matrix, Depth-First Search
- Shortest Path Visiting All Nodes Bit Manipulation, Graph, Bitmask
- Swim in Rising Water Array, Binary Search, Depth-First Search
- Word Ladder Hash Table, String
Companies that ask breadth-first search problems
- Amazon 145 problems on breadth-first search
- Google 110 problems on breadth-first search
- Microsoft 46 problems on breadth-first search
- Meta 35 problems on breadth-first search
- Bloomberg 8 problems on breadth-first search
- Adobe 5 problems on breadth-first search
- Airbnb 5 problems on breadth-first search
- Flipkart 5 problems on breadth-first search
- LinkedIn 5 problems on breadth-first search
- Samsung 5 problems on breadth-first search
- Snapchat 5 problems on breadth-first search
- Uber 5 problems on breadth-first search
Next topic: Depth-First Search