Clone Graph

The problem

Implement `cloneGraph(node)` for a connected undirected graph given as `Node { val, neighbors }` objects. Return a deep copy — none of the cloned nodes' `neighbors` arrays may point back into the original graph.

`null` is its own base case: an empty graph clones to itself, `if (!node) return node`, no traversal needed.

The approach

There's no adjacency object to index into here — each node already carries its own neighbours, so BFS reads `cur.neighbors` directly instead of `graph[cur]`. Everything else about the loop (queue, pop from the front, iterate neighbours) is the same shape as every earlier BFS in this log.

A single `Map<oldNode, newNode>` covers two jobs a separate `visited` Set would normally split: `map.has(nei)` is the visited check, and `map.get(nei)` is simultaneously the lookup that hands back the actual clone whenever another node needs to point at it.

A node's clone is created exactly once — seeded for the source before the loop starts, then inside the `!map.has(nei)` branch for everyone else — but the wiring line, `map.get(cur).neighbors.push(map.get(nei))`, runs on every edge encountered, including edges back to an already-cloned node. Skipping the *creation* but never the *wiring* for revisited neighbours is what keeps the copy a graph instead of collapsing it into a spanning tree.

The solution

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (!node) return node
    const map = new Map()
    const q = [node]
    map.set(node, new Node(node.val))

    while (q.length) {
        const cur = q.shift()
        for (let nei of cur.neighbors) {
            if (!map.has(nei)) {
                map.set(nei, new Node(nei.val))
                // works as a visited set also
                q.push(nei)
            }
            map.get(cur).neighbors.push(map.get(nei))
        }
    }

    return map.get(node)
};

Time O(V + E)Space O(V)