BFS (Breadth-First Search) Interview Questions
Last updated 2026-11-19
Breadth-first search explores a graph in rings: all vertices one edge away, then two edges away, and so on. That makes it the default tool for shortest path problems where every move costs the same, and it shows up constantly in grid and puzzle questions.
The problems below go from minimum tree depth to bitmask BFS, each with Python and Java code, complexity and edge cases. For the surrounding theory read graph interview questions. When edges have different weights the right tool becomes Dijkstra.
| Data structure | Queue (deque in Python, ArrayDeque in Java) |
|---|---|
| Cost | O(V + E) |
| Best for | Fewest steps in unweighted graphs |
| Variants | Multi-source, 0-1 BFS, state-space BFS |
The pattern and when to spot it
The signal words are minimum number of moves, steps, turns, rolls or transformations. If each move has equal cost, BFS gives the answer the first time the target is dequeued. Iterate by level, taking len(queue) at the start of each round, whenever you must count steps or stop at a depth.
Many questions hide a graph. A lock, a word list or a number puzzle has no explicit edges, but states and legal moves define one. Several starting points that spread simultaneously, such as rotting oranges, call for multi-source BFS: enqueue every source at distance 0 before the loop. When edge costs are only 0 or 1, use a deque and push zero-cost neighbours to the front.
Mistakes that cost marks
- Marking visited on dequeue instead of enqueue, which duplicates queue entries and can blow up time.
- Using a Python list with pop(0), which is O(n). Use collections.deque.
- Counting a level too many or too few at the end of the loop.
- Using BFS on weighted edges and getting a wrong shortest path.
- Forgetting that the state may need more than the node, for example node plus bitmask of visited nodes.
BFS (Breadth-First Search) Interview Questions: questions with worked answers
1 Minimum depth of a binary tree
easyBFS finds the first leaf level by level, so the first node with no children gives the answer without visiting the rest of the tree. A DFS must explore everything and must not treat a null child as a leaf. Time O(n) worst case, space O(w). Edge cases: empty tree is 0, a chain where the minimum depth equals the height, a node with one child is not a leaf.
pythonfrom collections import deque def min_depth(root): if not root: return 0 dq, depth = deque([root]), 1 while dq: for _ in range(len(dq)): n = dq.popleft() if not n.left and not n.right: return depth if n.left: dq.append(n.left) if n.right: dq.append(n.right) depth += 1javaint minDepth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); int depth = 1; while (!q.isEmpty()) { for (int i = q.size(); i > 0; i--) { TreeNode n = q.poll(); if (n.left == null && n.right == null) return depth; if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right); } depth++; } return depth; }2 Shortest path in a binary matrix
mediumFrom (0,0) to (n-1,n-1) moving in 8 directions through cells with 0. BFS gives the fewest cells. Mark a cell visited when you enqueue it, by writing 1 into the grid or keeping a visited array. Time O(n^2), space O(n^2). Edge cases: start or end blocked (return -1), a 1 by 1 grid with value 0 (answer 1), no route.
pythonfrom collections import deque def shortest_path(grid): n = len(grid) if grid[0][0] or grid[n-1][n-1]: return -1 dq, grid[0][0] = deque([(0, 0, 1)]), 1 while dq: r, c, d = dq.popleft() if r == n - 1 and c == n - 1: return d for dr in (-1, 0, 1): for dc in (-1, 0, 1): nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0: grid[nr][nc] = 1 dq.append((nr, nc, d + 1)) return -1javaint shortestPath(int[][] g) { int n = g.length; if (g[0][0] == 1 || g[n-1][n-1] == 1) return -1; Queue<int[]> q = new ArrayDeque<>(); q.add(new int[]{0, 0, 1}); g[0][0] = 1; while (!q.isEmpty()) { int[] t = q.poll(); if (t[0] == n - 1 && t[1] == n - 1) return t[2]; for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) { int nr = t[0] + dr, nc = t[1] + dc; if (nr >= 0 && nr < n && nc >= 0 && nc < n && g[nr][nc] == 0) { g[nr][nc] = 1; q.add(new int[]{nr, nc, t[2] + 1}); } } } return -1; }3 Rotting oranges: minutes until none are fresh
mediumThis is multi-source BFS. Enqueue every rotten orange at time 0, count fresh ones, then spread level by level. Each level is one minute. If fresh oranges remain at the end, return -1. Time O(R * C), space O(R * C). Edge cases: no fresh oranges (0), fresh oranges unreachable (-1), no rotten oranges but fresh ones present (-1), do not count the last empty level as a minute.
pythonfrom collections import deque def oranges_rotting(grid): R, C = len(grid), len(grid[0]) dq, fresh = deque(), 0 for r in range(R): for c in range(C): if grid[r][c] == 2: dq.append((r, c)) elif grid[r][c] == 1: fresh += 1 minutes = 0 while dq and fresh: for _ in range(len(dq)): r, c = dq.popleft() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 dq.append((nr, nc)) minutes += 1 return minutes if fresh == 0 else -1javaint orangesRotting(int[][] g) { int R = g.length, C = g[0].length, fresh = 0, minutes = 0; Queue<int[]> q = new ArrayDeque<>(); for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) { if (g[r][c] == 2) q.add(new int[]{r, c}); else if (g[r][c] == 1) fresh++; } int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; while (!q.isEmpty() && fresh > 0) { for (int i = q.size(); i > 0; i--) { int[] t = q.poll(); for (int[] d : dirs) { int nr = t[0] + d[0], nc = t[1] + d[1]; if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) { g[nr][nc] = 2; fresh--; q.add(new int[]{nr, nc}); } } } minutes++; } return fresh == 0 ? minutes : -1; }4 Distance of each cell to the nearest 0
mediumStarting a BFS from every 1 would be O(n^2 m^2). Reverse the viewpoint: enqueue all the 0 cells with distance 0 and expand outward. The first time a cell is reached is its shortest distance. Time O(R * C), space O(R * C). Edge cases: no zeros (input promises at least one), all zeros, a single cell.
pythonfrom collections import deque def update_matrix(mat): R, C = len(mat), len(mat[0]) dist = [[-1] * C for _ in range(R)] dq = deque() for r in range(R): for c in range(C): if mat[r][c] == 0: dist[r][c] = 0 dq.append((r, c)) while dq: r, c = dq.popleft() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 dq.append((nr, nc)) return distjavaint[][] updateMatrix(int[][] mat) { int R = mat.length, C = mat[0].length; int[][] dist = new int[R][C]; Queue<int[]> q = new ArrayDeque<>(); for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) { if (mat[r][c] == 0) q.add(new int[]{r, c}); else dist[r][c] = -1; } int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; while (!q.isEmpty()) { int[] t = q.poll(); for (int[] d : dirs) { int nr = t[0] + d[0], nc = t[1] + d[1]; if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] == -1) { dist[nr][nc] = dist[t[0]][t[1]] + 1; q.add(new int[]{nr, nc}); } } } return dist; }5 Word ladder: shortest transformation sequence
mediumTreat each word as a vertex, with edges between words that differ in one letter. BFS from the begin word, generating neighbours by replacing each character with a to z and checking a set of valid words. Remove words from the set when visited. Return the number of words on the path. Time O(N * L * 26) for N words of length L, space O(N * L). Edge cases: end word absent from the list (0), begin equal to end, words of different lengths, begin word not in the list (allowed).
pythonfrom collections import deque def ladder_length(begin, end, words): words = set(words) if end not in words: return 0 dq, steps = deque([begin]), 1 while dq: for _ in range(len(dq)): w = dq.popleft() if w == end: return steps for i in range(len(w)): for ch in 'abcdefghijklmnopqrstuvwxyz': nw = w[:i] + ch + w[i+1:] if nw in words: words.remove(nw) dq.append(nw) steps += 1 return 0javaint ladderLength(String begin, String end, List<String> list) { Set<String> words = new HashSet<>(list); if (!words.contains(end)) return 0; Queue<String> q = new ArrayDeque<>(); q.add(begin); int steps = 1; while (!q.isEmpty()) { for (int k = q.size(); k > 0; k--) { String w = q.poll(); if (w.equals(end)) return steps; char[] cs = w.toCharArray(); for (int i = 0; i < cs.length; i++) { char old = cs[i]; for (char ch = 'a'; ch <= 'z'; ch++) { cs[i] = ch; String nw = new String(cs); if (words.remove(nw)) q.add(nw); } cs[i] = old; } } steps++; } return 0; }6 Open the lock: minimum turns for a four-wheel combination lock
mediumStates are four-digit strings from 0000, each move turns one wheel up or down by one with wraparound, and dead ends are forbidden. BFS over at most 10^4 states gives the fewest turns. Time O(10^4 * 8), space O(10^4). Edge cases: target 0000, 0000 itself a dead end (-1), target unreachable because it is surrounded by dead ends.
pythonfrom collections import deque def open_lock(deadends, target): dead = set(deadends) if '0000' in dead: return -1 seen, dq, turns = {'0000'}, deque(['0000']), 0 while dq: for _ in range(len(dq)): s = dq.popleft() if s == target: return turns for i in range(4): d = int(s[i]) for nd in ((d + 1) % 10, (d - 1) % 10): t = s[:i] + str(nd) + s[i+1:] if t not in seen and t not in dead: seen.add(t); dq.append(t) turns += 1 return -1javaint openLock(String[] deadends, String target) { Set<String> dead = new HashSet<>(Arrays.asList(deadends)); if (dead.contains("0000")) return -1; Set<String> seen = new HashSet<>(List.of("0000")); Queue<String> q = new ArrayDeque<>(List.of("0000")); int turns = 0; while (!q.isEmpty()) { for (int k = q.size(); k > 0; k--) { String s = q.poll(); if (s.equals(target)) return turns; for (int i = 0; i < 4; i++) { int d = s.charAt(i) - '0'; for (int nd : new int[]{(d + 1) % 10, (d + 9) % 10}) { String t = s.substring(0, i) + nd + s.substring(i + 1); if (!seen.contains(t) && !dead.contains(t)) { seen.add(t); q.add(t); } } } } turns++; } return -1; }7 Perfect squares: fewest squares summing to n
mediumModel the numbers 0 to n as vertices, with an edge from x to x + k*k. BFS from 0 reaches n in the fewest steps. A DP over n works too and has the same worst-case cost; BFS is the cleaner shortest-path framing. Time O(n sqrt n), space O(n). Edge cases: n equal to 0, n a perfect square (1), n equal to 1.
pythonfrom collections import deque def num_squares(n): seen, dq, steps = {0}, deque([0]), 0 while dq: steps += 1 for _ in range(len(dq)): x = dq.popleft() k = 1 while x + k * k <= n: y = x + k * k if y == n: return steps if y not in seen: seen.add(y); dq.append(y) k += 1 return 0javaint numSquares(int n) { boolean[] seen = new boolean[n + 1]; Queue<Integer> q = new ArrayDeque<>(); q.add(0); seen[0] = true; int steps = 0; while (!q.isEmpty()) { steps++; for (int i = q.size(); i > 0; i--) { int x = q.poll(); for (int k = 1; x + k * k <= n; k++) { int y = x + k * k; if (y == n) return steps; if (!seen[y]) { seen[y] = true; q.add(y); } } } } return 0; }8 Snakes and ladders: fewest dice rolls
hardFlatten the boustrophedon board into square numbers 1 to n^2 with a helper that converts a number to a row and column. From square s try s+1 to s+6; if the target cell holds a snake or ladder (value not -1), jump to it. BFS over squares gives the minimum rolls. Time O(n^2), space O(n^2). Edge cases: the board last square holding a snake, the first square holding a ladder, rows alternate direction, a jump is taken only once per roll (not chained).
pythonfrom collections import deque def snakes_and_ladders(board): n = len(board) def cell(s): r, c = divmod(s - 1, n) row = n - 1 - r col = c if r % 2 == 0 else n - 1 - c return row, col seen, dq, rolls = {1}, deque([1]), 0 while dq: for _ in range(len(dq)): s = dq.popleft() if s == n * n: return rolls for nx in range(s + 1, min(s + 6, n * n) + 1): r, c = cell(nx) dest = board[r][c] if board[r][c] != -1 else nx if dest not in seen: seen.add(dest); dq.append(dest) rolls += 1 return -1javaint snakesAndLadders(int[][] board) { int n = board.length, total = n * n; boolean[] seen = new boolean[total + 1]; Queue<Integer> q = new ArrayDeque<>(); q.add(1); seen[1] = true; int rolls = 0; while (!q.isEmpty()) { for (int k = q.size(); k > 0; k--) { int s = q.poll(); if (s == total) return rolls; for (int nx = s + 1; nx <= Math.min(s + 6, total); nx++) { int r = (nx - 1) / n, c = (nx - 1) % n; int row = n - 1 - r, col = r % 2 == 0 ? c : n - 1 - c; int dest = board[row][col] != -1 ? board[row][col] : nx; if (!seen[dest]) { seen[dest] = true; q.add(dest); } } } rolls++; } return -1; }9 Minimum obstacles to remove using 0-1 BFS
hardMoving into an empty cell costs 0 and into an obstacle costs 1. A deque handles this without a heap: push the neighbour to the front for a cost-0 edge and to the back for a cost-1 edge, and relax distances as in Dijkstra. This gives O(V + E) instead of O(E log V). Time O(R * C), space O(R * C). Edge cases: start equals end (0), a grid of all obstacles except the corners, using a distance array so a cell can be re-queued with a smaller cost.
pythonfrom collections import deque def minimum_obstacles(grid): R, C = len(grid), len(grid[0]) INF = float('inf') dist = [[INF] * C for _ in range(R)] dist[0][0] = 0 dq = deque([(0, 0)]) while dq: r, c = dq.popleft() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C: w = grid[nr][nc] if dist[r][c] + w < dist[nr][nc]: dist[nr][nc] = dist[r][c] + w if w == 0: dq.appendleft((nr, nc)) else: dq.append((nr, nc)) return dist[R-1][C-1]javaint minimumObstacles(int[][] g) { int R = g.length, C = g[0].length; int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE); dist[0][0] = 0; Deque<int[]> dq = new ArrayDeque<>(); dq.add(new int[]{0, 0}); int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; while (!dq.isEmpty()) { int[] t = dq.pollFirst(); for (int[] d : dirs) { int nr = t[0] + d[0], nc = t[1] + d[1]; if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; int w = g[nr][nc]; if (dist[t[0]][t[1]] + w < dist[nr][nc]) { dist[nr][nc] = dist[t[0]][t[1]] + w; if (w == 0) dq.addFirst(new int[]{nr, nc}); else dq.addLast(new int[]{nr, nc}); } } } return dist[R-1][C-1]; }10 Shortest path that visits every node of a graph
hardThe state is (current node, set of visited nodes) as a bitmask, so there are n * 2^n states. Start BFS from every node at once with only its own bit set. The first state with the full mask is the answer, and the BFS depth is the number of edges in the walk. Time O(n^2 * 2^n), space O(n * 2^n). Edge cases: a single node (0), revisiting nodes and edges is allowed, so a visited set over nodes alone is wrong, n up to about 12.
pythonfrom collections import deque def shortest_path_all(graph): n = len(graph) full = (1 << n) - 1 dq = deque((i, 1 << i) for i in range(n)) seen = set(dq) steps = 0 while dq: for _ in range(len(dq)): u, mask = dq.popleft() if mask == full: return steps for v in graph[u]: state = (v, mask | (1 << v)) if state not in seen: seen.add(state); dq.append(state) steps += 1 return 0javaint shortestPathAll(int[][] graph) { int n = graph.length, full = (1 << n) - 1; boolean[][] seen = new boolean[n][1 << n]; Queue<int[]> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) { q.add(new int[]{i, 1 << i}); seen[i][1 << i] = true; } int steps = 0; while (!q.isEmpty()) { for (int k = q.size(); k > 0; k--) { int[] t = q.poll(); if (t[1] == full) return steps; for (int v : graph[t[0]]) { int m = t[1] | (1 << v); if (!seen[v][m]) { seen[v][m] = true; q.add(new int[]{v, m}); } } } steps++; } return 0; }
Frequently asked questions
When should I use BFS instead of DFS?
Use BFS when you need the fewest steps in an unweighted graph or must process by level. Use DFS for exhaustive search, cycle detection, components and ordering problems.
Why does BFS give the shortest path?
It visits vertices in non-decreasing distance order, so the first time you reach a vertex is via a path with the fewest edges.
What is the space complexity of BFS?
O(V) in the worst case, since the queue and visited set can hold most of the vertices. For grids that is O(R * C).
How does BFS appear in coding rounds?
Mostly as grid shortest-path, multi-source spread and word-transformation problems. The DSA coding round guide lists what to prioritise.
Related guides
More in DSA Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions