Breadth-First Search
The Breadth-First Search Pattern
Explore level by level using a queue: all nodes at distance 1, then all at distance 2, and so on. Because levels are visited in order, the first time a node is reached is guaranteed to be by a shortest path.
Interactive problems
Free to open
How do you recognise a breadth-first search problem?
The question asks for the shortest path or minimum number of steps in an unweighted graph or grid, or for something computed per level ("level order traversal", "rightmost node of each row"). "Minimum number of moves" almost always means BFS.
What is the time complexity of the breadth-first search pattern?
O(V + E) time, O(V) space for the queue and visited set. On a grid that is O(rows × cols).
Breadth-First Search practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Breadth-First Search problems by difficulty and complexity
The difficulty, running time and extra space of every breadth-first search solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Introduction to BFS | Easy | Ω(n) | Θ(n) | O(n) | O(n) |
| BFS Overview | Easy | Ω(1) | Θ(n) | O(n) | O(n) |
| Binary Tree Level Order Sum | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Binary Tree Rightmost Node | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Binary Tree Zigzag Level Order Traversal | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Maximum Width of Binary Tree | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Graphs Overview | Easy | Ω(1) | Θ(V + E) | O(V + E) | O(V + E) |
| Minimum Knight Moves | Medium | Ω(1) | Θ(max(|x|, |y|)²) | O(max(|x|, |y|)²) | O(max(|x|, |y|)²) |
| Rotting Oranges | Medium | Ω(R × C) | Θ(R × C) | O(R × C) | O(R × C) |
| 01 Matrix | Medium | Ω(R × C) | Θ(R × C) | O(R × C) | O(R × C) |
| Bus Routes | Hard | Ω(1) | Θ(S) | O(S) | O(S) |
Related patterns and concepts
The underlying technique is covered from first principles in the breadth-first search lesson in the DSA visualizer curriculum. Breadth-First Search is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree