DFS (Depth-First Search) and BFS (Breadth-First Search) are like twin siblings — mentioning one always brings the other to mind. In practice, however, we use DFS far more often than BFS. So does that mean BFS is useless?
If the only goal of DFS/BFS is to visit every node in a tree or graph, then their capabilities are essentially the same, and we naturally prefer DFS for its simpler code and lower space complexity. That said, there are certain scenarios where DFS simply cannot do the job and only BFS will work. These are the two scenarios this article covers: “level-order traversal” and “shortest path.”
This article includes the following topics:
- Comparing the characteristics of DFS and BFS
- Applicable scenarios for BFS
- How to perform level-order traversal with BFS
- How to solve shortest path problems with BFS
DFS vs. BFS
Let’s first compare the code for DFS traversal and BFS traversal on a binary tree.
DFS traversal uses recursion:
void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
}BFS traversal uses a queue data structure:
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // In Java, queue "pop" is written as poll()
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}Just comparing the two snippets, the most obvious impression is: DFS traversal code is so much more concise than BFS! This is because recursion implicitly uses the system’s stack, so we don’t need to maintain a data structure ourselves. If all we need is a simple traversal of a binary tree, DFS is clearly the more convenient choice.
Although both DFS and BFS visit every node in the binary tree, they visit nodes in different orders.
This traversal order is the fundamental reason why BFS can be used to solve “level-order traversal” and “shortest path” problems. Below, we’ll walk through several example problems to see how BFS tackles level-order traversal and shortest path problems.
BFS Application 1: Level-Order Traversal
LeetCode 102. Binary Tree Level Order Traversal (Medium)
Given a binary tree, return the node values obtained by level-order traversal. Level-order traversal means visiting all nodes level by level, from left to right.
What is level-order traversal? Simply put, it means dividing the binary tree into layers and then traversing each layer from left to right:
At first glance, this traversal order looks the same as BFS, so we might think we can directly use BFS to get the level-order traversal result. However, the required output format of level-order traversal differs from that of BFS. Level-order traversal requires us to distinguish each level, meaning it returns a two-dimensional array. BFS traversal, on the other hand, produces a one-dimensional array with no way to distinguish levels.
So how do we separate BFS traversal results into layers? Let’s first observe how nodes are enqueued and dequeued during BFS traversal:
Let’s capture a specific moment during BFS traversal:
As you can see, the queue currently contains nodes 3, 4, and 5, which come from level 1 and level 2 respectively. At this point, level 1 nodes haven’t all been dequeued yet, but level 2 nodes have already entered, and nodes from both levels are adjacent in the queue. We cannot tell which level a node in the queue belongs to.
Therefore, we need to slightly modify the code. Before traversing each level, we first record the number of nodes currently in the queue (which is the number of nodes in this level), and then process all nodes of this level in one go.
// Level-order traversal of a binary tree
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
for (int i = 0; i < n; i++) {
// The variable i has no special meaning; it is only used to loop n times
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
}With this, we’ve transformed BFS traversal into level-order traversal. During the traversal, the process of enqueuing and dequeuing nodes looks like this:
As you can see, in each iteration of the while loop, all nodes of the current level are dequeued, and all nodes of the next level are enqueued. This achieves level-order traversal.
The final solution code is:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(level);
}
return res;
}BFS Application 2: Shortest Path
In a tree, the path between any two nodes is unique, but in a graph, there may be multiple paths between nodes — so which path is the shortest? This type of problem is called the shortest path problem. The shortest path problem is a classic application of BFS, and its approach is closely related to level-order traversal.
In a binary tree, BFS traverses level by level. The same applies to graphs. Starting from the source node, BFS first visits nodes at the first level (distance 1 from the source), then nodes at the second level (distance 2 from the source), and so on. As you can see, with BFS, nodes closer to the source are visited first, which allows us to find the shortest path to any given node.
Tip:
Many people instinctively think of “Dijkstra’s algorithm” the moment they see “shortest path.” So why can BFS traversal also find shortest paths?
The reason is that Dijkstra’s algorithm solves the weighted shortest path problem, whereas what we’re dealing with here is the unweighted shortest path problem. You can also think of it as every edge having a weight of 1. For this kind of shortest path problem, BFS is all you need.
In an interview setting, you’d probably rather write BFS than Dijkstra. After all, not many people can confidently say they’ll implement Dijkstra’s algorithm correctly.
Shortest path problems fall under graph algorithms. Since graphs can be complex to represent and describe, this article uses a simpler grid structure as a substitute. A grid is a special kind of graph that is straightforward to represent and traverse, making it a good choice for practice problems. On LeetCode, shortest path problems also predominantly use grid structures.
Shortest Path Example Walkthrough
LeetCode 1162. As Far from Land as Possible (Medium)
You are given an grid map
gridwhere each cell is marked as either 0 or 1. Here, 0 represents ocean and 1 represents land. Find an ocean cell such that its distance to the nearest land cell is maximized.The distance mentioned here is the “Manhattan distance.” The distance between two cells and is .
If the map contains only land or only ocean, return -1.
This problem is essentially about finding shortest paths in a grid structure. At the same time, it is also an “island problem,” where 1s and 0s in the grid represent land and ocean, simulating several islands.
In the previous article, we introduced the basic concepts of grid structures and DFS traversal on grids. Some of those concepts and techniques also apply to BFS traversal:
- The four neighbors of cell
(r, c)are:(r-1, c),(r+1, c),(r, c-1), and(r, c+1); - Use the
inAreafunction to check whether the current cell’s coordinates are within the grid bounds; - Mark traversed cells as 2 to avoid revisiting them.
If you’re not very familiar with grid structure properties or DFS traversal techniques on grids, you may want to review the previous article: LeetCode Example Problems | 12 Island Problems: DFS in Grid Structures.
The previous article covered DFS traversal on grids, so this article is a great opportunity to explain BFS traversal on grids. To solve shortest path problems, we first need to write the level-order traversal code. Following the binary tree level-order traversal code above, we can similarly write a grid level-order traversal:
// Level-order traversal on a grid
// Start traversing from cell (i, j)
void bfs(int[][] grid, int i, int j) {
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{r, c});
while (!queue.isEmpty()) {
int n = queue.size();
for (int i = 0; i < n; i++) {
int[] node = queue.poll();
int r = node[0];
int c = node[1];
if (r-1 >= 0 && grid[r-1][c] == 0) {
grid[r-1][c] = 2;
queue.add(new int[]{r-1, c});
}
if (r+1 < N && grid[r+1][c] == 0) {
grid[r+1][c] = 2;
queue.add(new int[]{r+1, c});
}
if (c-1 >= 0 && grid[r][c-1] == 0) {
grid[r][c-1] = 2;
queue.add(new int[]{r, c-1});
}
if (c+1 < N && grid[r][c+1] == 0) {
grid[r][c+1] = 2;
queue.add(new int[]{r, c+1});
}
}
}
}There are a few things to note about the level-order traversal code above:
- The elements in the queue are
int[]arrays, each of length 2, containing the row and column coordinates of a cell. - To avoid revisiting cells, we use the same technique as in DFS traversal: mark visited cells as 2. Note that we mark a cell as 2 before adding it to the queue. Think about it — why is that?
- We check whether a cell’s coordinates are within the grid bounds before adding it to the queue, to avoid enqueuing cells that “don’t exist.”
There is still room to optimize this grid traversal code. Since each cell has four neighbors, the code checks coordinate validity four times, which is a bit verbose. We can use a moves array to store the four directions of neighboring cells:
int[][] moves = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1},
};Then replace the four if-statements with a single loop:
for (int[][] move : moves) {
int r2 = r + move[0];
int c2 = c + move[1];
if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
grid[r2][c2] = 2;
queue.add(new int[]{r2, c2});
}
}With the level-order traversal code ready, let’s now see how to solve the shortest path problem in this question.
This problem asks us to find the ocean cell that is farthest from any land. Suppose there is only one land cell in the grid. We can start a level-order traversal from that land cell until all cells have been visited. The number of levels traversed equals the maximum distance of ocean cells.
But what if there are multiple land cells? One approach is to run a separate level-order traversal from each land cell, but this would be too expensive in terms of time.
BFS can start from multiple cells simultaneously. We can put all land cells into the initial queue at once and then begin level-order traversal. The effect of this traversal is shown below:
This traversal method is actually called “multi-source BFS.” The formal definition of multi-source BFS is not the focus of today’s discussion. You just need to remember that multi-source BFS is very convenient — simply put multiple source nodes into the initial queue at once.
Note that although the illustrations above use 1, 2, 3, 4 to indicate the level number in the traversal, in the actual code we don’t need to label each visited cell with its level number. We only need a single distance variable to track the current traversal level (i.e., the distance from land cells).
Finally, the solution code is:
public int maxDistance(int[][] grid) {
int N = grid.length;
Queue<int[]> queue = new ArrayDeque<>();
// Add all land cells to the queue
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
queue.add(new int[]{i, j});
}
}
}
// If the grid contains only land or only ocean, return -1
if (queue.isEmpty() || queue.size() == N * N) {
return -1;
}
int[][] moves = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1},
};
int distance = -1; // Track the current BFS level (distance)
while (!queue.isEmpty()) {
distance++;
int n = queue.size();
for (int i = 0; i < n; i++) {
int[] node = queue.poll();
int r = node[0];
int c = node[1];
for (int[] move : moves) {
int r2 = r + move[0];
int c2 = c + move[1];
if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
grid[r2][c2] = 2;
queue.add(new int[]{r2, c2});
}
}
}
}
return distance;
}
// Check whether coordinate (r, c) is inside the grid
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}Summary
As you can see, “BFS traversal,” “level-order traversal,” and “shortest path” are actually progressive concepts. By distinguishing each level during BFS traversal, we get level-order traversal. By tracking the level number during level-order traversal, we get shortest paths.
BFS traversal is a category of problems well worth revisiting and practicing repeatedly. On one hand, BFS traversal is a classic fundamental algorithm that deserves thorough mastery. On the other hand, we need to be able to analyze a problem statement and recognize that it’s asking for shortest paths, thereby knowing that BFS traversal is required.
This article only covered two very typical example problems. LeetCode has many more level-order traversal and shortest path problems.
Some variations of level-order traversal:
- LeetCode 103. Binary Tree Zigzag Level Order Traversal — Zigzag level-order traversal
- LeetCode 199. Binary Tree Right Side View — Find the rightmost node of each level
- LeetCode 515. Find Largest Value in Each Tree Row — Compute the maximum value of each level
- LeetCode 637. Average of Levels in Binary Tree — Compute the average value of each level
For shortest path problems, there are two more problems that also involve finding shortest paths in grid structures, very similar to the farthest distance from islands problem we discussed:
And there’s one problem that involves finding shortest paths in an actual graph structure:
After the explanations in this article, solving these problems should not be difficult.