Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

BFS with Queue
DSA

BFS with Queue

Understand how queues drive breadth-first search and level-by-level exploration.

A queue (FIFO) makes BFS explore level by level — first seen, first processed.

Focus on recognizing:

“Level by level” / “shortest path in unweighted graph” → queue

Pattern 1: Tree Level Order

Level order on [3,9,20,null,null,15,7] — each grid row is one queue drain. Press ▶ to animate.

Level-Order Traversal (BFS on a Tree)

Use a queue to visit a binary tree level by level. Freeze the queue size at the start of each round so you process exactly one level before the next round's children are added.

Tree [3,9,20,null,null,15,7]. Seed the queue with the root. Each round: note the current size, poll that many nodes, visit them, and enqueue their children. Watch the queue hold one whole level at a time — the level order [3,9,20,15,7] emerges naturally.

QUEUE VISUALIZER
Steps –
← DEQUEUE (Front)
3
ENQUEUE (Rear) →
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        queue = [root]
                      
                        2
                        while queue not empty:
                      
                        3
                          size = queue.length        // freeze level
                      
                        4
                          repeat size times:
                      
                        5
                            node = queue.poll(); visit node
                      
                        6
                            enqueue node.left, node.right
                      
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();          // freeze the level
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
    }

    return result;
}
from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        size = len(queue)         # freeze the level
        level = []

        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();          // freeze the level
        vector<int> level;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);

            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }

        result.push_back(level);
    }

    return result;
}
function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length) {
    const size = queue.length; // freeze the level
    const level = [];

    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

Capture queue.size() BEFORE the inner loop — children enqueued mid-loop belong to the NEXT level.

Pattern 2: Graph BFS (Shortest Path)

The queue explores in rings; first arrival = fewest edges.

BFS Shortest Path (Graph)

Breadth-First Search explores a graph level by level using a queue. The first time a node is reached, it is via the fewest edges — so BFS finds the shortest path in an unweighted graph in O(V + E).

Graph A→F. Seed the queue with A. Each step, dequeue a node and enqueue its unvisited neighbors. Watch the queue hold one 'ring' of the graph at a time, and the edges light up as discovery spreads. The distance to F is the number of rings popped before F is dequeued.

GRAPH VISUALIZER
Steps –
ABCDEF
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        queue = [start]; dist[start] = 0
                      
                        2
                        while queue:
                      
                        3
                          n = dequeue
                      
                        4
                          for nb in adj[n] not visited:
                      
                        5
                            dist[nb] = dist[n]+1; enqueue(nb)

Unweighted edges ⇒ BFS distance = shortest distance:

public int shortestPath(List<List<Integer>> graph,
                        int start, int end) {
    boolean[] visited = new boolean[graph.size()];
    Queue<int[]> queue = new LinkedList<>();   // [node, dist]

    queue.offer(new int[]{start, 0});
    visited[start] = true;

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();

        if (cur[0] == end) return cur[1];

        for (int next : graph.get(cur[0])) {
            if (!visited[next]) {       // mark ON enqueue
                visited[next] = true;
                queue.offer(new int[]{next, cur[1] + 1});
            }
        }
    }

    return -1;
}
from collections import deque

def shortest_path(graph, start, end):
    visited = [False] * len(graph)
    queue = deque([(start, 0)])
    visited[start] = True

    while queue:
        node, dist = queue.popleft()

        if node == end:
            return dist

        for nxt in graph[node]:
            if not visited[nxt]:   # mark ON enqueue
                visited[nxt] = True
                queue.append((nxt, dist + 1))

    return -1
int shortestPath(vector<vector<int>>& graph, int start, int end) {
    vector<bool> visited(graph.size(), false);
    queue<pair<int, int>> q;               // {node, dist}

    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        auto [node, dist] = q.front();
        q.pop();

        if (node == end) return dist;

        for (int next : graph[node]) {
            if (!visited[next]) {          // mark ON enqueue
                visited[next] = true;
                q.push({next, dist + 1});
            }
        }
    }

    return -1;
}
function shortestPath(graph, start, end) {
  const visited = new Array(graph.length).fill(false);
  const queue = [[start, 0]];
  visited[start] = true;

  while (queue.length) {
    const [node, dist] = queue.shift();

    if (node === end) return dist;

    for (const next of graph[node]) {
      if (!visited[next]) {
        // mark ON enqueue
        visited[next] = true;
        queue.push([next, dist + 1]);
      }
    }
  }

  return -1;
}

Mark visited when ENQUEUING, not when popping — otherwise nodes enter the queue twice.

Pattern 3: Multi-Source BFS

Seed ALL sources together — they share the waves and halve the time.

Rotting Oranges (Multi-Source BFS)

Every rotten orange enters the queue simultaneously. Each minute, rot spreads to adjacent fresh oranges. Find the minimum minutes until no fresh orange remains.

Grid: R=rotten, O=fresh, F=wall. Seed ALL rotten cells at minute 0. Each wave spreads rot one cell outward. Watch cells change from O to R as waves propagate.

GRID VISUALIZER
Steps –
R
O
O
O
F
O
O
O
O
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        queue = all initially rotten
                      
                        2
                        minute = 0
                      
                        3
                        while queue not empty:
                      
                        4
                          process whole level, minute++
                      
                        5
                          fresh neighbours → rot & enqueue

Seed the queue with ALL sources; distances become “nearest source”:

public int[][] nearestExit(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == 0)           // every source
                queue.offer(new int[]{r, c});

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();

        for (int[] d : dirs) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && grid[nr][nc] == -1) {   // unvisited land
                grid[nr][nc] = grid[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }

    return grid;
}
from collections import deque

def nearest_exit(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:    # every source
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()

        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
                    and grid[nr][nc] == -1:  # unvisited land
                grid[nr][nc] = grid[r][c] + 1
                queue.append((nr, nc))

    return grid
vector<vector<int>> nearestExit(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int,int>> q;

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == 0)       // every source
                q.push({r, c});

    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && grid[nr][nc] == -1) {  // unvisited
                grid[nr][nc] = grid[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    return grid;
}
function nearestExit(grid) {
  const rows = grid.length,
    cols = grid[0].length;
  const queue = [];

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 0) queue.push([r, c]); // every source

  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  while (queue.length) {
    const [r, c] = queue.shift();

    for (const [dr, dc] of dirs) {
      const nr = r + dr,
        nc = c + dc;

      if (
        nr >= 0 &&
        nr < rows &&
        nc >= 0 &&
        nc < cols &&
        grid[nr][nc] === -1
      ) {
        grid[nr][nc] = grid[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return grid;
}

Common Mistakes

Using a stack instead of a queue.

LIFO turns BFS into DFS — you lose level boundaries and shortest-path guarantees.

Marking visited at pop time.

The same node gets enqueued multiple times before being marked — exponential blowup on dense graphs.

Recomputing the level size inside the loop.

size must be frozen once per level; queue.length changes as you enqueue children.

Complexity

Graph shapeTimeSpace
TreeO(n)O(width)
Graph V, EO(V + E)O(V)
Grid n×mO(n·m)O(n·m)

My Private Notes

Notes are auto-saved locally to this device.