Autocoder

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 structureQueue (deque in Python, ArrayDeque in Java)
CostO(V + E)
Best forFewest steps in unweighted graphs
VariantsMulti-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

BFS (Breadth-First Search) Interview Questions: questions with worked answers

  1. 1

    Minimum depth of a binary tree

    easy

    BFS 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.

    python
    from 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 += 1
    java
    int 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. 2

    Shortest path in a binary matrix

    medium

    From (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.

    python
    from 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 -1
    java
    int 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. 3

    Rotting oranges: minutes until none are fresh

    medium

    This 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.

    python
    from 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 -1
    java
    int 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. 4

    Distance of each cell to the nearest 0

    medium

    Starting 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.

    python
    from 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 dist
    java
    int[][] 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. 5

    Word ladder: shortest transformation sequence

    medium

    Treat 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).

    python
    from 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 0
    java
    int 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. 6

    Open the lock: minimum turns for a four-wheel combination lock

    medium

    States 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.

    python
    from 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 -1
    java
    int 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. 7

    Perfect squares: fewest squares summing to n

    medium

    Model 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.

    python
    from 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 0
    java
    int 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. 8

    Snakes and ladders: fewest dice rolls

    hard

    Flatten 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).

    python
    from 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 -1
    java
    int 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. 9

    Minimum obstacles to remove using 0-1 BFS

    hard

    Moving 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.

    python
    from 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]
    java
    int 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. 10

    Shortest path that visits every node of a graph

    hard

    The 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.

    python
    from 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 0
    java
    int 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

See all in this section