Leetcode/Guide/BFS

Contents

Breadth-First Search (BFS) is a fundamental graph and tree traversal algorithm.
It explores nodes level by level — visiting all neighbors before moving deeper.
BFS is perfect when you need the shortest path, minimum steps, or level-order traversal.

---

🧠 Core Idea

• BFS uses a queue (FIFO — First In, First Out).
• Start from a source node and:
  1. Visit the node.
  2. Add all its unvisited neighbors to the queue.
  3. Dequeue the next node and repeat.

This guarantees that you explore all nodes at distance k before any at distance k+1.

---

Example 1 — BFS Traversal in a Binary Tree

function breadthFirstTraversal(rootNode) {
  if (!rootNode) return [];

  const queue = [rootNode];
  const result = [];

  while (queue.length > 0) {
    const currentNode = queue.shift();
    result.push(currentNode.value);

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

  return result;
}

// Demo
const tree = {
  value: 1,
  left: { value: 2, left: { value: 4 }, right: { value: 5 } },
  right: { value: 3, left: { value: 6 }, right: { value: 7 } }
};

console.log(breadthFirstTraversal(tree)); 
// Output: [1, 2, 3, 4, 5, 6, 7]

✅ Why this works:
We process nodes in the order they are discovered — ensuring we visit all nodes level by level.

---

Example 2 — Level Order Traversal (Tree with Levels)

If we want to separate nodes by levels, we can track each level explicitly.

function levelOrderTraversal(rootNode) {
  if (!rootNode) return [];

  const queue = [rootNode];
  const levels = [];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.shift();
      currentLevel.push(currentNode.value);

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

    levels.push(currentLevel);
  }

  return levels;
}

// Demo
console.log(levelOrderTraversal(tree));
// Output: [1], [2, 3], [4, 5, 6, 7](/wiki/1],_[2,_3],_[4,_5,_6,_7)

✅ Why this works:
We process all nodes of one level before starting the next — controlled by levelSize.

---

Example 3 — BFS in a Graph (Adjacency List)

Graphs can be cyclic or disconnected, so we track visited nodes to prevent infinite loops.

function bfsGraphTraversal(graph, startNode) {
  const visited = new Set();
  const queue = [startNode];
  const result = [];

  visited.add(startNode);

  while (queue.length > 0) {
    const currentNode = queue.shift();
    result.push(currentNode);

    const neighbors = graph[currentNode] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

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

console.log(bfsGraphTraversal(graph, 'A')); 
// Output: ['A', 'B', 'C', 'D', 'E', 'F']

✅ Why this works:
The queue ensures we explore nodes in increasing order of distance from the start node.

---

Example 4 — Shortest Path in an Unweighted Graph

BFS naturally finds the shortest path (in terms of edge count) in an unweighted graph.

function shortestPathUnweighted(graph, startNode, targetNode) {
  const queue = [startNode](/wiki/startNode);
  const visited = new Set([startNode]);

  while (queue.length > 0) {
    const currentPath = queue.shift();
    const lastNode = currentPath[currentPath.length - 1];

    if (lastNode === targetNode) {
      return currentPath; // shortest path found
    }

    const neighbors = graph[lastNode] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([...currentPath, neighbor]);
      }
    }
  }

  return null; // no path found
}

// Demo
console.log(shortestPathUnweighted(graph, 'A', 'F')); 
// Output: ['A', 'C', 'F']

✅ Why this works:
Since BFS expands uniformly outward, the first time we reach the target node, it’s guaranteed to be via the shortest path.

---

Example 5 — BFS in a Grid (2D Matrix)

Common for maze and island problems.
Each cell has up to 4 neighbors (up, down, left, right).

function bfsInGrid(matrix, startRow, startCol) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;
  const visited = Array.from({ length: numRows }, () => Array(numCols).fill(false));
  const queue = [startRow, startCol](/wiki/startRow,_startCol);
  const directions = [
    [1, 0],  // down
    [-1, 0], // up
    [0, 1],  // right
    [0, -1]  // left
  ];

  visited[startRow][startCol] = true;
  const result = [];

  while (queue.length > 0) {
    const [row, col] = queue.shift();
    result.push(matrix[row][col]);

    for (const [dRow, dCol] of directions) {
      const newRow = row + dRow;
      const newCol = col + dCol;

      const isInBounds = newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols;
      if (isInBounds && !visited[newRow][newCol]) {
        visited[newRow][newCol] = true;
        queue.push([newRow, newCol]);
      }
    }
  }

  return result;
}

// Demo
const grid = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];
console.log(bfsInGrid(grid, 0, 0));
// Output: [1, 2, 4, 3, 5, 7, 6, 8, 9] (order may vary by implementation)

✅ Why this works:
The queue ensures every cell is explored in the order it’s reached, preventing redundant visits.

---

🧩 Summary Table

---

🚀 Key Takeaways

• BFS = Queue + Visited tracking
• Perfect for shortest paths, level traversals, and minimum steps
• Time complexity: O(V + E) (V = vertices, E = edges)
• Space complexity: O(V) due to the queue and visited structures
• Common in:
  • Trees
  • Graphs
  • Grids
  • Puzzles (mazes, word ladders, etc.)

Mastering BFS helps you solve a wide range of traversal and pathfinding problems efficiently.