Breadth-First Search (BFS) Explained With Easy Tree Examples

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root]; // Queue — FIFO

  while (queue.length > 0) {
    const levelSize = queue.length; // all nodes at the current level
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // dequeue (process current node)
      level.push(node.val);

      if (node.left)  queue.push(node.left);  // enqueue left child
      if (node.right) queue.push(node.right); // enqueue right child
    }

    result.push(level); // all nodes at this level are done
  }

  return result;
}

//       3
//      / \
//     9   20
//        / \
//       15   7
//
// Step-by-step:
// Queue: [3] → level=[3], enqueue 9,20 → result=[[3]]
// Queue: [9,20] → level=[9,20], enqueue 15,7 → result=[[3],[9,20]]
// Queue: [15,7] → level=[15,7], no children → result=[[3],[9,20],[15,7]]

levelOrder(root); // → [[3], [9,20], [15,7]]

// Variant: Right side view (last node of each level)
function rightSideView(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      if (i === levelSize - 1) result.push(node.val); // last node = visible from right
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

rightSideView(root); // → [3, 20, 7]

function shortestPath(graph, start, end) {
  const visited = new Set([start]);
  const queue = [[start, [start]]]; // each entry: [currentNode, pathSoFar]

  while (queue.length > 0) {
    const [node, path] = queue.shift();

    if (node === end) return path; // first time we reach 'end' = shortest path

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null; // no path exists
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

shortestPath(graph, 'A', 'F'); // → ['A', 'C', 'F']  (2 edges, shortest)
// BFS considers A's neighbors: B, C
// Then B's neighbors: D, E (A already visited)
// Then C's neighbors: F ← found! Path: A→C→F

// Shortest distance only (without path):
function shortestDistance(graph, start, end) {
  const visited = new Set([start]);
  const queue = [[start, 0]]; // [node, distance]

  while (queue.length > 0) {
    const [node, dist] = queue.shift();
    if (node === end) return dist;
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1; // unreachable
}

function updateMatrix(mat) {
  const m = mat.length, n = mat[0].length;
  const dist = Array.from({length: m}, () => new Array(n).fill(Infinity));
  const queue = [];

  // Multi-source BFS: initialize all 0 cells as sources with distance 0
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (mat[r][c] === 0) {
        dist[r][c] = 0;
        queue.push([r, c]);
      }
    }
  }

  const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; // down, up, right, left

  while (queue.length > 0) {
    const [r, c] = queue.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
          dist[nr][nc] > dist[r][c] + 1) {  // found shorter distance
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return dist;
}

// Matrix: [[0,0,0],[0,1,0],[1,1,1]]
// Result: [[0,0,0],[0,1,0],[1,2,1]]
// The center bottom cell has distance 2 from nearest 0

// ❌ Slow for large inputs: queue.shift() is O(n)
while (queue.length > 0) {
  const node = queue.shift(); // O(n) — shifts all elements left
  // ...
}

// ✅ Fast: use a pointer — O(1) dequeue
const queue = [startNode];
let head = 0; // points to front of queue

while (head < queue.length) {
  const node = queue[head++]; // O(1) — just increment pointer
  // process node...
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      visited.add(neighbor);
      queue.push(neighbor); // O(1) amortized
    }
  }
}

// For competitive programming, consider a proper deque:
class Deque {
  constructor() { this.data = {}; this.head = 0; this.tail = 0; }
  push(val) { this.data[this.tail++] = val; }
  shift() { return this.data[this.head++]; }
  get length() { return this.tail - this.head; }
}