BFS

// 1) BFS on a binary tree — level order
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function bfs(root) {
    if (!root) return [];
    const out = [];
    const queue = [root];
    while (queue.length) {
        const node = queue.shift();
        out.push(node.val);
        if (node.left)  queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return out;
}

// 2) Level-by-level
function levels(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    while (queue.length) {
        const level = [];
        const size  = queue.length;
        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;
}

// 3) BFS on a graph (adjacency list)
function bfsGraph(graph, start) {
    const visited = new Set([start]);
    const queue   = [start];
    const order   = [];
    while (queue.length) {
        const node = queue.shift();
        order.push(node);
        for (const neighbour of graph[node] ?? []) {
            if (!visited.has(neighbour)) {
                visited.add(neighbour);
                queue.push(neighbour);
            }
        }
    }
    return order;
}

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

// 4) Shortest path (unweighted graph) — BFS naturally finds shortest in edges
function shortestPath(graph, start, end) {
    if (start === end) return [start];

    const visited = new Set([start]);
    const queue   = [[start, [start]]];

    while (queue.length) {
        const [node, path] = queue.shift();
        for (const neighbour of graph[node] ?? []) {
            if (visited.has(neighbour)) continue;
            if (neighbour === end)      return [...path, neighbour];
            visited.add(neighbour);
            queue.push([neighbour, [...path, neighbour]]);
        }
    }
    return null;
}

shortestPath(graph, 'A', 'F');   // ['A', 'B', 'D', 'F']

// 5) Grid BFS (most common interview pattern)
function shortestGridPath(grid, start, end) {
    const rows = grid.length, cols = grid[0].length;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    const visited = Array.from({length: rows}, () => new Array(cols).fill(false));
    const [sr, sc] = start;
    visited[sr][sc] = true;

    const queue = [[sr, sc, 0]];   // [row, col, distance]

    while (queue.length) {
        const [r, c, d] = queue.shift();
        if (r === end[0] && c === end[1]) return d;

        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (visited[nr][nc] || grid[nr][nc] === '#')        continue;
            visited[nr][nc] = true;
            queue.push([nr, nc, d + 1]);
        }
    }
    return -1;
}

const grid = [
    ['.','.','.','#','.'],
    ['.','#','.','#','.'],
    ['.','#','.','.','.'],
    ['.','.','.','#','.'],
];
shortestGridPath(grid, [0, 0], [3, 4]);   // 7

// 6) Number of islands (flood fill via BFS)
function countIslands(grid) {
    const rows = grid.length, cols = grid[0].length;
    const visited = Array.from({length: rows}, () => new Array(cols).fill(false));
    let count = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1' && !visited[r][c]) {
                count++;
                bfsIsland(grid, r, c, visited);
            }
        }
    }
    return count;
}

function bfsIsland(grid, r, c, visited) {
    const rows = grid.length, cols = grid[0].length;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    const queue = [[r, c]];
    visited[r][c] = true;
    while (queue.length) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
            const nr = cr + dr, nc = cc + dc;
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (visited[nr][nc] || grid[nr][nc] !== '1')        continue;
            visited[nr][nc] = true;
            queue.push([nr, nc]);
        }
    }
}

// 7) Word ladder (BFS on a graph of words)
function ladderLength(begin, end, wordList) {
    const dict = new Set(wordList);
    if (!dict.has(end)) return 0;

    const queue = [[begin, 1]];
    const visited = new Set([begin]);

    while (queue.length) {
        const [word, length] = queue.shift();
        if (word === end) return length;

        for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) {
                const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                if (dict.has(next) && !visited.has(next)) {
                    visited.add(next);
                    queue.push([next, length + 1]);
                }
            }
        }
    }
    return 0;
}

// 8) Bidirectional BFS — search from both ends, meet in the middle
// Roughly halves the search space (sqrt(N) vs N).
function bidirectionalBfs(graph, start, end) {
    if (start === end) return 0;
    let s = new Set([start]);
    let e = new Set([end]);
    let visited = new Set([...s, ...e]);
    let steps = 0;

    while (s.size && e.size) {
        // Expand the smaller frontier (optimisation)
        if (s.size > e.size) [s, e] = [e, s];
        const next = new Set();
        for (const node of s) {
            for (const neighbour of graph[node] ?? []) {
                if (e.has(neighbour)) return steps + 1;
                if (!visited.has(neighbour)) {
                    visited.add(neighbour);
                    next.add(neighbour);
                }
            }
        }
        s = next;
        steps++;
    }
    return -1;
}

// 9) Python — collections.deque is the right tool
# from collections import deque
# def bfs(graph, start):
#     visited, queue = {start}, deque([start])
#     while queue:
#         node = queue.popleft()              # O(1) — popping from list is O(N)
#         for neighbour in graph[node]:
#             if neighbour not in visited:
#                 visited.add(neighbour)
#                 queue.append(neighbour)

// 10) When to use BFS vs DFS
// BFS — when you need:
//   ✅ Shortest path on unweighted graph (edges count)
//   ✅ Level-order traversal
//   ✅ Finding the nearest match
//   ✅ Layered exploration
// DFS — when you need:
//   ✅ Path enumeration / backtracking
//   ✅ Topological sort
//   ✅ Cycle detection
//   ✅ Lower memory in deep, narrow graphs

// BFS uses O(W) memory where W is max width (level size).
// DFS uses O(D) memory where D is max depth.

// 11) Common bugs
//   • Using array .shift() — O(N) in JS (each pop is linear); use deque-like structure
//   • Visiting nodes by adding to visited AFTER pop — re-queues duplicates
//   • Forgetting to handle the start === end case
//   • Inefficient queue: in Python, list.pop(0) is O(N); use deque
//   • For weighted graphs, BFS gives WRONG shortest path; use Dijkstra

// 12) Complexity
// Time:  O(V + E) — visits each node and edge once
// Space: O(V)     — visited set + queue

// 13) Advanced patterns
// 0-1 BFS         — deque-based BFS for graphs with 0/1 edge weights
// Multi-source BFS — start from multiple nodes simultaneously (rotten oranges, walls and gates)
// BFS + state    — node + state in queue (different state = different node)
// BFS on grid with teleporters — same shape, different neighbour function

// 14) Multi-source BFS (e.g. spread of fire)
function shortestToZero(grid) {
    const rows = grid.length, cols = grid[0].length;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    const dist = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
    const queue = [];

    // Initial queue — all zeros
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 0) { dist[r][c] = 0; queue.push([r, c]); }
        }
    }

    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) continue;
            if (dist[nr][nc] > dist[r][c] + 1) {
                dist[nr][nc] = dist[r][c] + 1;
                queue.push([nr, nc]);
            }
        }
    }
    return dist;
}

function bfs(start, graph) {
    const seen = new Set([start]);
    const q = [start];
    while (q.length) {
        const u = q.shift();
        for (const v of graph.get(u) ?? []) if (!seen.has(v)) { seen.add(v); q.push(v); }
    }
    return seen;
}