[Algorithm] 12. Breadth-First Search (BFS)

12. Breadth-First Search (BFS)

DFS : using stack
Ensures predictable memory usage and efficient processing.

BFS : using queue
keeping track of the depth level
works fine for small or balanced trees but is not as efficient in deep or skewed trees due to recursion depth limits

Use BFS (Queue-based) if you need strict level-order traversal.
Use DFS (Stack-based) if you need a depth-first approach but want to simulate level tracking.

1.Binary Tree Level Order Traversal (LeetCode #102)

BFS

function levelOrderBFS(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  
  while(queue.length > 0) {
	// Number of nodes at the same level
	const cntNodesAtSameLevel = queue.length 
	// Valuses of the same level 
	const valsOnThisLevel:number[] = []; 

	for(let i = 0 ; i < levelSize; i++){
		const node = queue.shift()!;
        valsOnThisLevel.push(node.val);
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
	}
	result.push(valsOnThisLevel)
  }

  return result
}

DFS : Recursive
Caution: Deep recursion calls, which could cause a stack overflow in unbalanced trees.

function levelOrderRecursive(root: TreeNode | null): number[][] {
  const result: number[][] = [];
  
  function dfs(node:TreeNode|null, level: number){
	if(!node) return ;
    if(!result[level]) result[level] = [];
    result[level].push(node.val); 
    level++;
    dfs(node.left, level);
    dfs(node.right, level);
  }

  dfs(root, 0);
  return result; 
}

DFS : Iterative

function levelOrderDFSIterative(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result : number[][]= [];
  const stack: {node:TreeNode, level:number}[] = [{node: root, level: 0}]
  while(stack.length > 0){
	const {node, level} = stack.pop()!;
    if(!result[level]) result[level] = [];
    result[level].push(node.val);
    if(node.left) stack.push({node: node.left, level: level+1})
	if(node.right) stack.push({ node: node.right, level: level + 1 });
  }

  return result;
}

2.Rotting Oranges (LeetCode #994)

using freshOrangeCnt (efficient one)

// using freshOrangeCnt
// Time Complexity: O(n * m)
// Space Complexity: O(n * m)

// Step 1 : Find Rotten Oranges
// Add all rotten oranges (2) to a queue and mark them as visited

// Step 2 : BFS Spread
// Process each orange in the queue, infecting its fresh neighbors (1) in 4 directions.
// Count BFS levels to track time (count).

// Step 3 : Final check
// If fresh oranges (1) remain, return -1.
// Otherwise, return count (time taken).
function orangesRotting(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let minutes = 0,
    freshCnt = 0;
  const rottenOrangesPosQueue: [number, number][] = [];

  // Step 1: Enqueue all rotten oranges
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        rottenOrangesPosQueue.push([r, c]);
      } else if (grid[r][c] === 1) {
        freshCnt++;
      }
    }
  }

  if (freshCnt === 0) return 0;

  // 4 directional top / bottom / left / right
  const directions = [
    [0, 1],
    [0, -1],
    [-1, 0],
    [1, 0],
  ];

  // Step 2: BFS to rot fresh oranges
  while (rottenOrangesPosQueue.length > 0 && freshCnt > 0) {
    let size = rottenOrangesPosQueue.length;

    for (let i = 0; i < size; i++) {
      const [row, col] = rottenOrangesPosQueue.shift()!;

      // make adjacent fresh orange rotten in 4 direction
      for (const [dx, dy] of directions) {
        const newX = row + dx;
        const newY = col + dy;
        if (
          newX < rows && // new row positoin x is under row length
          newY < cols && // new col positoin y is under col length
          newX >= 0 &&
          newY >= 0 &&
          // !visited[newX][newY] && // not visited
          grid[newX][newY] === 1 // fresh one
        ) {
          grid[newX][newY] = 2; // make it rotten
          rottenOrangesPosQueue.push([newX, newY]);
          freshCnt--;
        }
      }
    }

    minutes++;
  }

  return freshCnt === 0 ? minutes : -1;
}

using visited array( one more for loop)

// Time Complexity: O(n * m)
// Space Complexity: O(n * m)
function orangesRottingVistedList(grid: number[][]): number {
  // Step 1 : Find Rotten Oranges
  // Add all rotten oranges (2) to a queue and mark them as visited

  // Step 2 : BFS Spread
  // Process each orange in the queue, infecting its fresh neighbors (1) in 4 directions.
  // Count BFS levels to track time (count).

  // Step 3 : Final check
  // If fresh oranges (1) remain, return -1.
  // Otherwise, return count (time taken).

  const rowLength = grid.length;
  const colLength = grid[0].length;
  let minutes = 0;

  const rottenOrangesPosQueue: [number, number][] = [];
  const visited: boolean[][] = Array.from({ length: rowLength }, () =>
    Array(colLength).fill(false)
  );

  // Step 1: Enqueue all rotten oranges
  for (let i = 0; i < rowLength; i++) {
    for (let j = 0; j < colLength; j++) {
      if (grid[i][j] === 2) {
        rottenOrangesPosQueue.push([i, j]);
        visited[i][j] = true;
      }
    }
  }

  // 4 directional top / bottom / left / right
  const directions = [
    [0, 1],
    [0, -1],
    [-1, 0],
    [1, 0],
  ];

  // Step 2: BFS to rot fresh oranges
  while (rottenOrangesPosQueue.length > 0) {
    let size = rottenOrangesPosQueue.length;

    for (let i = 0; i < size; i++) {
      const [row, col] = rottenOrangesPosQueue.shift()!;

      // make adjacent fresh orange rotten in 4 direction
      for (const [dx, dy] of directions) {
        const newX = row + dx;
        const newY = col + dy;
        if (
          newX < rowLength && // new row positoin x is under row length
          newY < colLength && // new col positoin y is under col length
          newX >= 0 &&
          newY >= 0 &&
          // !visited[newX][newY] && // not visited
          grid[newX][newY] === 1 // fresh one
        ) {
          grid[newX][newY] = 2; // make it rotten
          rottenOrangesPosQueue.push([newX, newY]);
          visited[newX][newY] = true;
        }
      }
    }

    minutes++;
  }

  // Step 3: Check for remaining fresh oranges
  for (let i = 0; i < rowLength; i++) {
    for (let j = 0; j < colLength; j++) {
      if (grid[i][j] === 1) return -1;
    }
  }

  return minutes === -1 ? 0 : minutes;
}

3.Word Ladder (LeetCode #127)

BFS

// readable
function ladderLength(
  beginWord: string,
  endWord: string,
  wordList: string[]
): number {
  const wordSet = new Set(wordList);

  if (!wordSet.has(endWord)) return 0;

  const queue: [string, number][] = [[beginWord, 1]];
  const visited = new Set<string>();

  visited.add(beginWord);

  // Perform BFS
  while (queue.length > 0) {
    const [currentWord, level] = queue.shift()!;

    for (let i = 0; i < currentWord.length; i++) {
      const originalChar = currentWord[i];

      // Try relacing the charater with every letter from 'a' to 'z'
      for (
        let charCode = "a".charCodeAt(0);
        charCode <= "z".charCodeAt(0);
        charCode++
      ) {
        const newChar = String.fromCharCode(charCode);
        if (newChar === originalChar) continue;

        const newWord =
          currentWord.slice(0, i) + newChar + currentWord.slice(i + 1);

        if (wordSet.has(newWord) && !visited.has(newWord)) {
          if (newWord === endWord) {
            return level + 1;
          }

          queue.push([newWord, level + 1]);
          visited.add(newWord);
        }
      }
    }
  }

  return 0;
}

shorter

function ladderLengthShorter(
  beginWord: string,
  endWord: string,
  wordList: string[]
): number {
  const wordSet = new Set(wordList);

  if (!wordSet.has(endWord)) return 0;
  let queue: [string, number][] = [[beginWord, 1]];
  while (queue.length > 0) {
    const [word, steps] = queue.shift()!;
    if (word === endWord) return steps;

    for (let i = 0; i < word.length; i++) {
      for (let i = "a".charCodeAt(0); i < "z".charCodeAt(0); i++) {
        let newWord =
          word.slice(0, i) + String.fromCharCode(i) + word.slice(i + 1);
        if (wordSet.has(newWord)) {
          queue.push([newWord, steps + 1]);
          wordSet.delete(newWord); // 하니씩 삭제하면서 검증
        }
      }
    }
  }
  return 0;
}