Back to All Algorithms
Breadth-First Search (BFS)
Category: Tree / Graph | Time: O(n) | Space: O(w)
Visualization
Visual representation of the data structure
About Breadth-First Search (BFS)
A graph traversal algorithm that explores the neighbor nodes first, before moving to the next level neighbors. It's often used to find the shortest path in an unweighted graph.
Code Editor
The code is for reference. Editing it won't affect the visualization.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Variable State
{
"status": "Starting Traversal"
}Breadth-First Search (BFS): How It Works
Last updated October 28, 2026
Overview
Breadth-first search (BFS), also called level-order traversal on trees, visits every node on one level before moving to the next. It uses a queue: take the node at the front, visit it, and add its children to the back. Because the queue is first-in, first-out, nodes come out in exactly the order of their distance from the root.
That distance-ordering property is why BFS finds shortest paths in unweighted graphs: the first time it reaches a node, it has used the fewest possible edges. On trees, it is the natural way to print level by level or find the minimum depth.
On the default tree, BFS visits 10, 5, 15, 2, 7, 12, 18. The queue variable in the dry run shows how 5 and 15 are queued while 10 is processed, and how the grandchildren join behind them.
Step by step
- Put the root in a queue.
- While the queue is not empty, remove the node at the front and visit it.
- Add its left child, then its right child, to the back of the queue if they exist.
- Repeat until the queue is empty.
Complexity
| Case | Cost | Why |
|---|---|---|
| Time | O(n) | Each node is enqueued and dequeued once. For graphs: O(V + E). |
| Space | O(w) | w is the maximum width of the tree; up to about n/2 in a complete tree. |
When to use it
- Shortest path in unweighted graphs or grids (mazes, word ladders, knight moves).
- Level-order problems: printing a tree by levels, finding the right-side view, or the minimum depth.
- Finding everything within k steps, such as friends-of-friends in a social network.
Common mistakes
- Using
Array.shift()as the dequeue in JavaScript is O(n) per call; for large inputs use an index pointer or a real queue. - On graphs, mark nodes as visited when they are enqueued, not when they are dequeued, or the same node can be queued many times.
- BFS can use a lot of memory on wide trees, where depth-first traversal would be cheaper.
Worked Example: Breadth-First Search (BFS) Dry Run
Generated from the same trace that drives the visualizer above, using the default input.
A dry run is the best way to check your understanding of Breadth-First Search (BFS): follow each row, predict the next one, and compare. The run below takes 31 steps in total. The Line column refers to the line numbers in the code listing above.
- Input
- Binary tree (see the input box above)
- Result
- final_path = [10, 5, 15, 2, 7, 12, 18]
| Step | Line | What happens |
|---|---|---|
| 1 | 1 | status = Starting Traversal |
| 2 | 3 | action = Enqueue root (10), queue = [10] |
| 3 | 5 | queue = [10], condition = 1 > 0 |
| 4 | 6 | action = Dequeue 10, queue = [], current_node = 10 |
| 5 | 8 | action = Visit 10, visited_path = [10] |
| 6 | 10 | action = Enqueue left child (5), queue = [5] |
| 7 | 12 | action = Enqueue right child (15), queue = [5, 15] |
| 8 | 5 | queue = [5, 15], condition = 2 > 0 |
| 9 | 6 | action = Dequeue 5, queue = [15], current_node = 5 |
| 10 | 8 | action = Visit 5, visited_path = [10, 5] |
| 11 | 10 | action = Enqueue left child (2), queue = [15, 2] |
| 12 | 12 | action = Enqueue right child (7), queue = [15, 2, 7] |
| 13 | 5 | queue = [15, 2, 7], condition = 3 > 0 |
| 14 | 6 | action = Dequeue 15, queue = [2, 7], current_node = 15 |
| 15 | 8 | action = Visit 15, visited_path = [10, 5, 15] |
| 16 | 10 | action = Enqueue left child (12), queue = [2, 7, 12] |
| 17 | 12 | action = Enqueue right child (18), queue = [2, 7, 12, 18] |
| 18 | 5 | queue = [2, 7, 12, 18], condition = 4 > 0 |
| 19 | 6 | action = Dequeue 2, queue = [7, 12, 18], current_node = 2 |
| 20 | 8 | action = Visit 2, visited_path = [10, 5, 15, 2] |
| 21 | 5 | queue = [7, 12, 18], condition = 3 > 0 |
| 22 | 6 | action = Dequeue 7, queue = [12, 18], current_node = 7 |
| 23 | 8 | action = Visit 7, visited_path = [10, 5, 15, 2, 7] |
| 24 | 5 | queue = [12, 18], condition = 2 > 0 |
| 25 | 6 | action = Dequeue 12, queue = [18], current_node = 12 |
| 26 | 8 | action = Visit 12, visited_path = [10, 5, 15, 2, 7, 12] |
| 27 | 5 | queue = [18], condition = 1 > 0 |
| 28 | 6 | action = Dequeue 18, queue = [], current_node = 18 |
| 29 | 8 | action = Visit 18, visited_path = [10, 5, 15, 2, 7, 12, 18] |
| 30 | 5 | queue = [], condition = 0 > 0 |
| 31 | 15 | final_path = [10, 5, 15, 2, 7, 12, 18] |
Frequently Asked Questions
About Breadth-First Search (BFS)
What is Breadth-First Search (BFS)?
BFS is a graph traversal algorithm that explores neighbor nodes first, before moving to the next level neighbors. It starts at a source node and explores all of its neighbors at the present depth prior to moving on to the nodes at the next depth level. It uses a queue to keep track of the next location to visit.
How does BFS work?
BFS starts with a source node, adds it to a queue, and marks it as visited. Then, it enters a loop that continues as long as the queue is not empty. In each iteration, it dequeues a node, visits it, and enqueues all of its unvisited neighbors. This process guarantees that nodes are visited level by level.
What is the time complexity of BFS?
The time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges. Every vertex and every edge is explored exactly once.
What is the space complexity of BFS?
The space complexity is O(W), where W is the maximum width of the tree or graph. In the worst-case scenario (a complete binary tree), the last level can contain up to n/2 nodes, so the space can be proportional to the number of nodes.
What is the primary use case for BFS?
The most well-known application of BFS is to find the shortest path between two nodes in an unweighted graph. Because it explores level by level, the first time it reaches a target node, it is guaranteed to have found a shortest path.
How does BFS compare to Depth-First Search (DFS)?
BFS explores level by level (horizontally), while DFS explores branch by branch (vertically). BFS is better for finding the shortest path in unweighted graphs, while DFS is often used for cycle detection, pathfinding in mazes, and topological sorting.
Can BFS be implemented recursively?
While technically possible, it's very unnatural and inefficient. BFS is fundamentally an iterative algorithm that relies on a queue data structure to manage the order of visitation. The iterative approach is standard practice.
Where can I learn more?
You can find a more detailed explanation on GeeksforGeeks.
Related Interview Questions
Practice with real problems