Intro
At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:
- Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
- Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
- Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
- Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
- Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
- Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
- Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
- Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).
Today I will be covering Breadth First Search (BFS) in tree/graph traversals.
When to use BFS
Recognize a problem that can be solved with BFS by these signs:
- The problem requires the shortest path, minimum steps, fewest moves, earliest time, or minimum operations in an unweighted graph, grid, tree, or similar structure (this is the single strongest signal - BFS is the only standard algorithm that guarantees shortest path in unweighted settings)
- All edges/moves have equal cost (unit cost / cost = 1, if costs vary -> Dijkstra / 0-1 BFS / A* instead)
- The solution needs level-by-level processing, results grouped by distance, or exploration ordered by increasing distance from the start(s) (includes collecting nodes per level, processing by depth, or any "by distance k" requirement)
- The problem has multi-source starting points (multiple cells/nodes begin simultaneously at distance/time 0) OR it involves spreading / propagation / infection / flooding from one or more origins over time
Basically you are expanding your search by filling the solution space as close to the starting point as possible.
Rule of thumb: if the problem says 'shortest', 'minimum steps', 'level by level' or 'multi-source spread' in an unweighted graph/grid/tree, then BFS is your friend.
Example 1
In the previous post we've used a maze problem to demonstrate the use of depth first search (DFS). There we had to find if a maze can be solved, any solution would do, and it did find a solution which was ludicrously long. Now we're being asked to find the shortest path to escape the maze.
Problem statement: Given a 2D grid representing a maze (0 = open path, 1 = wall), find the minimum number of steps to go from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). You can move in 4 directions (up, down, left, right), but cannot go through walls or outside the grid. Return the shortest path length, or -1 if no path exists. Assume (0,0) and (m-1,n-1) are open (0).
Example grid (same as in the DFS post):
var maze = new int[][]
{
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 0, 1, 0],
[1, 0, 0, 0]
};
Since we've already solved a maze question with DFS, why not do it here as well? Here is a possible attempt:
int minSteps = int.MaxValue;
int ShortestPath(int[][] maze, int row, int col, int steps = 0)
{
int m = maze.Length;
int n = maze[0].Length;
if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
return -1;
if (row == m - 1 && col == n - 1)
{
minSteps = Math.Min(minSteps, steps);
return minSteps;
}
// Mark as visited by setting to 1 (temporary)
maze[row][col] = 1;
// Explore all 4 directions
ShortestPath(maze, row - 1, col, steps + 1); // up
ShortestPath(maze, row + 1, col, steps + 1); // down
ShortestPath(maze, row, col - 1, steps + 1); // left
ShortestPath(maze, row, col + 1, steps + 1); // right
// Backtrack: unmark
maze[row][col] = 0;
return minSteps == int.MaxValue ? -1 : minSteps;
}
var result = ShortestPath(maze, 0, 0);
Console.WriteLine(result);
The output is 6, which is correct, so is this a good solution? Let's see what the complexity of the algorithm is.
The time complexity is O(4n*m) in worst cases (branching factor 4 - the directions - and depth up to m*n). This times out even on small grids! Then the marking and unmarking of things is also adding complexity and stack space: O(n*m), which would lead to stack overflows.
But what's worse is that this may not find the shortest path at all! And if it does, it explores longer paths when shorter ones exist.
With BFS, this doesn't happen. The standard form of a BFS solution looks like this:
public int SomeBfs(TreeNode root) { // or int[][] grid, etc.
if (root == null) return 0;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
// bool[,] visited = ... if needed
int level = 0;
while (queue.Count > 0) {
int size = queue.Count; // process current level
for (int i = 0; i < size; i++) {
TreeNode node = queue.Dequeue();
// Do something with node (e.g. collect value)
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
level++;
}
return level - 1; // example: max depth
}
The inner loop processes one full level before moving deeper - that's the BFS guarantee - but it's not needed most of the time, since you can just dequeue node by node. The point is that by using a queue, you ensure a first in first out (FIFO) approach, proceeding one level further only when the previous one has been explored.
Let's see how that works for our problem:
int ShortestPath(int[][] maze)
{
if (maze == null || maze.Length == 0)
return -1;
var m = maze.Length;
var n = maze[0].Length;
if (maze[0][0] == 1 || maze[m - 1][n - 1] == 1)
return -1;
var visited = new bool[m, n];
var queue = new Queue<(int, int, int)>();
queue.Enqueue((0, 0, 0)); // row, col, steps
visited[0, 0] = true;
int[][] directions = [
[ -1, 0 ],
[ 1, 0 ],
[ 0, -1 ],
[ 0, 1 ]
]; // up, down, left, right
while (queue.Count > 0)
{
var (r, c, steps) = queue.Dequeue();
if (r == m - 1 && c == n - 1)
return steps;
foreach (var dir in directions)
{
var nr = r + dir[0];
var nc = c + dir[1];
if (nr >= 0 && nr < m
&& nc >= 0 && nc < n
&& maze[nr][nc] == 0 && !visited[nr, nc])
{
visited[nr, nc] = true;
queue.Enqueue((nr, nc, steps + 1));
}
}
}
return -1; // no path
}
Note the tuple used as the queue item type! In this kind of solutions, that type needs to hold all the information needed to process a step. In our case, it's the row and column position plus the number of steps to get there.
The execution is simple: start with (0,0,0 - top-left corner) in the queue, then process and remove items in the queue one by one and add four new ones, one for each direction. Constraints like never process the same cell twice, keeping in the borders of the grid and FIFO processing guarantee that when a solution is found, it's the shortest.
If you try to visualize how that works, imagine each cell as it is placed in the queue changing it's color to red:
If you have ever used a graphical image editor, you may recognize the "fill" feature, where you select a color to fill up the space taken by another color. That's another common problem for this kind of algorithm.
So, let's check the complexity. Time: O(n*m) as each cell is visited at most once. Space: O(n*m) for the visited array and the queue. BFS explores by increasing distance, so the first time it reaches the end is guaranteed to be the shortest path. No backtracking needed, and it stops as soon as possible.
Switching between DFS and BFS
I was planning on writing a separate post about this, but the setup is the same, so I will just make this another chapter here.
We've learned to use the stack of the programming language to do DFS, but for BFS we had to use our own data structure, the queue, where an item contains all of the information required to run a step. We also learned that the stack is limited (usually to around 1MB) so even a working DFS program might lead to a stack overflow if the input data is too large. This would not happen in the case of the BFS example. The queue would just take up as much space as it needs within the available memory. This means that using the default recursive execution mechanism of the programming language is making the solution brittle.
If only we could use the same mechanism we used for BFS to write a DFS solution! Well, if you think about it, the only reason the BFS is doing things level by level is the FIFO implementation of the queue. Replacing the queue with a stack (wait, stack? yes, it's the same thing as the one used by the recursive function calling) moves us from FIFO to LIFO (last in, first out) and translates BFS solutions to DFS solutions.
Replacing in our code above a Queue<T> with a Stack<T>, Enqueue with Push and Dequeue with Pop, you execute it and get the same result! But if you visualize the path the code takes, it looks like this:
Only the shape of the maze makes this finish in the same number of steps as the BFS one, so this is not a valid solution for the problem, but this simplifies the development model a little. All you need to do is write the same kind of code and choose the right data structure to generate a DFS or a BFS solution. And bonus points, you can tell the interviewers that you would never trust the tiny recursive execution stack to be large enough for your code.
Let's see the DFS example from the previous post, written with our own stack implementation:
bool HasPath(int[][] maze)
{
int m = maze.Length;
int n = maze[0].Length;
var visited = new bool[m][];
for (int i = 0; i < m; i++)
visited[i] = new bool[n];
var stack = new Stack<(int row, int col)>();
stack.Push((0, 0));
while (stack.TryPop(out var cell))
{
var (row, col) = cell;
if (row < 0 || row >= m
|| col < 0 || col >= n
|| maze[row][col] == 1)
continue;
if (row == m - 1 && col == n - 1)
return true;
// avoid cycles by not visiting the same cell again
if (visited[row][col])
continue;
// mark the cell as visited
visited[row][col] = true;
stack.Push((row-1, col));
stack.Push((row+1, col));
stack.Push((row, col-1));
stack.Push((row, col+1));
}
return false;
}
var result = HasPath(maze);
Console.WriteLine(result);
This solution is completely equivalent, but using no recursion whatsoever. Note that the item type is just a pair of row and column, since the maze is a local parameter. To do that with recursion you need to declare a local function, which makes the code a lot less readable. Also, while maintaining the logic of the original method, this is not optimal. We are adding items in the stack and only checking the values in the item when we get it off the stack. If you check that before adding them to the stack, the code will become more efficient and even more readable.
The caveat, though, is that if you write the code badly, you have to wait for a memory overflow to know you fouled it up.
Example 2
Let take a really nasty problem: Shortest Path Visiting All Nodes. This is a classic hard problem in the interviews, so let's see how it goes.
Problem statement: You are given an undirected, connected graph with n nodes labeled from 0 to n-1 and a list of edges (as adjacency list: graph[i] = list of neighbors of i). Return the length of the shortest path that visits every node exactly once (you can start at any node and return to visited nodes if needed, but must cover all). The path length is the number of edges traversed. If no such path exists, return -1 (but since the graph is connected, it always does).
Constraints
- 1 ≤ n ≤ 12
- 0 ≤ graph[i].Length < n (no self-loops, possible multiple edges but assume simple)
- The graph is undirected and connected.
Naive solution:
int[][] graph1 = [ [1, 2, 3], [0], [0], [0] ];
// Nodes: 0 connected to 1,2,3; others only to 0.
// Shortest path covering all: e.g., 3-0-1-0-2 (visits all, length 4)
// Output: 4
int[][] graph2 = [ [1], [0, 2, 4], [1, 3, 4], [2], [1, 2] ];
//A more connected graph.
//Shortest path: e.g., 0-1-2-3-4 (length 4, but check if shorter exists)
//Output: 4
int minLength = int.MaxValue;
int ShortestPathLength(int[][] graph)
{
int n = graph.Length;
for (int start = 0; start < n; start++)
{
bool[] visited = new bool[n];
visited[start] = true;
Dfs(graph, start, 1, visited, 0); // node, visited count, path length
}
return minLength == int.MaxValue ? -1 : minLength;
}
void Dfs(int[][] graph, int node, int visitedCount, bool[] visited, int length)
{
if (visitedCount == visited.Length)
{
minLength = Math.Min(minLength, length);
return;
}
foreach (int nei in graph[node])
{
if (!visited[nei])
{
visited[nei] = true;
Dfs(graph, nei, visitedCount + 1, visited, length + 1);
visited[nei] = false; // backtrack
}
else
{
// Even allow revisits? But this explodes
Dfs(graph, nei, visitedCount, visited, length + 1);
}
}
}
Console.WriteLine(ShortestPathLength(graph1));
Console.WriteLine(ShortestPathLength(graph2));
The DFS one has the issues we've seen with the simple maze example above:
- exponential complexity explosion: O(n! * n)
- no guarantee that the found path is shortest
- backtracking is inefficient
- missing state as it doesn't track visited nodes efficiently
This fails with a terrible stack overflow exception. Of course, we could implement this with a Stack<T> and reach a much worse timeout/memory overflow exception.
Let's take a look at the BFS solution with the correct implementation:
int[][] graph1 = [ [1, 2, 3], [0], [0], [0] ];
// Nodes: 0 connected to 1,2,3; others only to 0.
// Shortest path covering all: e.g., 3-0-1-0-2 (visits all, length 4)
// Output: 4
int[][] graph2 = [ [1], [0, 2, 4], [1, 3, 4], [2], [1, 2] ];
//A more connected graph.
//Shortest path: e.g., 0-1-2-3-4 (length 4, but check if shorter exists)
//Output: 4
int ShortestPathLength(int[][] graph)
{
var n = graph.Length;
var target = (1 << n) - 1; // all nodes visited: 111...1 (n bits)
Queue<(int node, int mask, int steps)> queue = new();
var visited = new bool[n, 1 << n]; // node + mask visited?
// Start from every node (multi-source)
for (var i = 0; i < n; i++)
{
var initMask = 1 << i;
queue.Enqueue((i, initMask, 0));
visited[i, initMask] = true;
}
while (queue.Count > 0)
{
var (node, mask, steps) = queue.Dequeue();
if (mask == target)
return steps;
foreach (var nei in graph[node])
{
var newMask = mask | (1 << nei); // visit nei
if (!visited[nei, newMask])
{
visited[nei, newMask] = true;
queue.Enqueue((nei, newMask, steps + 1));
}
}
}
return -1; // though always connected
}
Console.WriteLine(ShortestPathLength(graph1));
Console.WriteLine(ShortestPathLength(graph2));
Bonus: uses a bit mask to store the visited nodes for each step. Interview people love bit operations and premature optimizations.
The solution starts from every single node to find the shortest path, a classical BFS sign. In the beginning the queue has an item for each node, a mask with a bit for that node only and a counter for the steps. Then it removes items one by one and adds items for each of the neighbors, mask updated, counter incremented. Again, because we use a FIFO queue, when we first get to the target (the mask is filled with 1s), it's guaranteed to have a the smallest count of steps.
Note that this would also fail if n were allowed to be much larger than 12.
Time complexity: O(n * 2n * E / n) ≈ O(n * 2n) since E small - for n=12, ~50k states * avg degree ~3-5 = ~200k operations, fast.
Space complexity: O(n * 2n) for visited (~50k bools).
Example 3
Let's do one more: Binary Tree Level Order Traversal.
Problem statement: Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Return the result as a list of lists, where each inner list contains the node values at that level.
Example:
Output: [[3],[9,20],[15,7]]
Constraints:
- The number of nodes in the tree is in the range [0, 2000].
- -1000 ≤ Node.val ≤ 1000
So here's the code:
IList<IList<int>> LevelOrder(TreeNode root)
{
var result = new List<IList<int>>();
if (root == null)
{
return result;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
// Number of nodes at current level
int levelSize = queue.Count;
// Values for this level
var currentLevel = new List<int>();
// Process all nodes at the current level
for (int i = 0; i < levelSize; i++)
{
TreeNode node = queue.Dequeue();
currentLevel.Add(node.Value);
// Enqueue children for the next level
if (node.Left != null)
{
queue.Enqueue(node.Left);
}
if (node.Right != null)
{
queue.Enqueue(node.Right);
}
}
result.Add(currentLevel);
}
return result;
}
TreeNode root = new()
{
Value = 3,
Left = new() { Value = 9 },
Right = new()
{
Value = 20,
Left = new() { Value = 15 },
Right = new() { Value = 7 }
}
};
var result = LevelOrder(root);
Console.WriteLine($"[ {string.Join(", ",result.Select(a=> $"[{string.Join(", ",a)}]"))} ]");
The time complexity is O(n) - we visit each node exactly once, the space complexity is O(w) - where w is the maximum width of the tree (size of the queue at the widest level), worst-case O(n) for a complete tree.
The inner for loop over queue.Count ensures we process one full level before moving deeper - that's what gives the level-by-level order. Without the level-size loop, you'd get a flat list instead of grouped by level.
DFS (recursive) can also collect levels (by passing depth parameter), but BFS feels more natural and intuitive for this exact requirement.
Conclusion
Exploring the solution space using graph traversal is a very powerful technique used in a lot of contexts. Go depth or breadth first, depending on the requirements, in order to get to the optimal solution.
- BFS: shortest path guarantee, but higher memory (queue can hold O(n) nodes)
- DFS: simpler recursion, lower memory in deep-but-narrow graphs, but no shortest-path promise
- When BFS loses: very deep trees, leading to recursion stack overflow risk (rare)
- Hybrid tip: use BFS when correctness > simplicity
