DFS

// 1) DFS on a tree (recursive)
class TreeNode {
    constructor(val, children = []) { this.val = val; this.children = children; }
}

function dfsTree(node, visit) {
    if (!node) return;
    visit(node);                                  // pre-order
    for (const child of node.children) dfsTree(child, visit);
    // post-order action here
}

// 2) DFS on a graph (with visited set)
function dfsGraph(graph, start, visit) {
    const visited = new Set();
    (function go(u) {
        if (visited.has(u)) return;
        visited.add(u);
        visit(u);
        for (const v of graph[u] ?? []) go(v);
    })(start);
    return visited;
}

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

// 3) Iterative DFS (explicit stack — avoids recursion limits)
function dfsIterative(graph, start) {
    const visited = new Set();
    const stack   = [start];
    while (stack.length) {
        const u = stack.pop();
        if (visited.has(u)) continue;
        visited.add(u);
        for (const v of graph[u] ?? []) {
            if (!visited.has(v)) stack.push(v);
        }
    }
    return visited;
}

// 4) Cycle detection in a directed graph (white / grey / black)
function hasCycle(graph) {
    const WHITE = 0, GREY = 1, BLACK = 2;
    const color = new Map();
    for (const u of Object.keys(graph)) color.set(u, WHITE);

    function dfs(u) {
        color.set(u, GREY);
        for (const v of graph[u] ?? []) {
            if (color.get(v) === GREY) return true;       // back-edge → cycle
            if (color.get(v) === WHITE && dfs(v)) return true;
        }
        color.set(u, BLACK);
        return false;
    }

    return Object.keys(graph).some((u) => color.get(u) === WHITE && dfs(u));
}

// 5) Topological sort (post-order DFS, reversed)
function topoSort(graph) {
    const visited = new Set();
    const order   = [];
    function dfs(u) {
        if (visited.has(u)) return;
        visited.add(u);
        for (const v of graph[u] ?? []) dfs(v);
        order.push(u);                                  // record on the way out
    }
    Object.keys(graph).forEach(dfs);
    return order.reverse();
}

const deps = {
    bootstrap: ['styles', 'routes'],
    styles:    ['theme'],
    routes:    ['auth'],
    auth:      [],
    theme:     [],
};
topoSort(deps);              // ['bootstrap', 'styles', 'theme', 'routes', 'auth']

// 6) Connected components in an undirected graph
function components(graph) {
    const seen  = new Set();
    const comps = [];
    for (const u of Object.keys(graph)) {
        if (seen.has(u)) continue;
        const comp = [];
        (function go(x) {
            if (seen.has(x)) return;
            seen.add(x);
            comp.push(x);
            for (const v of graph[x]) go(v);
        })(u);
        comps.push(comp);
    }
    return comps;
}

// 7) Grid DFS — flood fill / island count
function numIslands(grid) {
    const R = grid.length, C = grid[0].length;
    let count = 0;

    function sink(r, c) {
        if (r < 0 || c < 0 || r >= R || c >= C || grid[r][c] !== 1) return;
        grid[r][c] = 2;                                  // mark visited
        sink(r + 1, c); sink(r - 1, c);
        sink(r, c + 1); sink(r, c - 1);
    }

    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (grid[r][c] === 1) { count++; sink(r, c); }
        }
    }
    return count;
}

// 8) Recursion-depth pitfall — convert to iterative for big inputs
// JS default stack ~10-15k frames; deep linked lists or paths blow it.
// Iterative + explicit stack scales linearly with heap.

// 9) Time / space complexity
//   • Tree:  O(n) time, O(h) stack space, h = height
//   • Graph: O(V + E) time, O(V) visited + O(V) recursion stack

// 10) DFS vs BFS — when to use which
//   DFS: existence questions, topological order, cycle detection, backtracking
//   BFS: shortest path on unweighted graphs, level-order, minimum steps

// 11) Common bugs
//   • Forgetting the visited set on a graph → infinite recursion on cycles
//   • Mutating the visited container while iterating outer loop
//   • Reverse-of-post-order: ALWAYS return order.reverse() for topo
//   • Off-by-one in grid bounds checks
//   • Recursing without a base case → stack overflow

function dfs(u, graph, seen = new Set()) {
    if (seen.has(u)) return;
    seen.add(u);
    for (const v of graph.get(u) ?? []) dfs(v, graph, seen);
    return seen;
}