Graph Clone

You're given a reference to one node in a connected, undirected graph. Return a deep copy of the whole graph: a brand-new set of node objects with the same values and the same connections, sharing nothing with the original. Think of it as snapshotting a social network or a road map — you want an independent copy you can mutate without touching the original.

The catch is that a graph is not a tree. It can contain cycles (A links to B, B links back to A) and nodes that are shared by several others. A copy routine that just follows neighbours and recurses will revisit the same node forever, or stamp out two separate copies of a node that was supposed to be one.

Signature

// A node is a plain object: an integer value plus a list of neighbour nodes.
type Node = { val: number, neighbors: Node[] };

// node: a reference to ONE node in the graph (the graph is connected,
//   so every node is reachable from it). May be null.
// returns: the cloned node corresponding to `node`, or null if node is null.
function graphClone(node: Node | null): Node | null;

The edges are undirected, represented as two directed links: if A and B are connected, then A is in B.neighbors and B is in A.neighbors.

Examples

// A triangle: 1—2, 2—3, 3—1. Each node lists the other two as neighbours.
const a = { val: 1, neighbors: [] };
const b = { val: 2, neighbors: [] };
const c = { val: 3, neighbors: [] };
a.neighbors = [b, c];
b.neighbors = [a, c];
c.neighbors = [a, b];

const copy = graphClone(a);
copy.val;                       // 1
copy !== a;                     // true  — a new object
copy.neighbors[0] !== b;        // true  — neighbours are new objects too
copy.neighbors[0].neighbors[0]; // the clone of `a` again (the cycle is preserved)

// A single node with no neighbours.
graphClone({ val: 7, neighbors: [] }); // → { val: 7, neighbors: [] }  (a NEW object)

// null in, null out.
graphClone(null); // → null

Notes

• Deep copy, not shallow. Every node in the result must be a new object. clone !== original, and the same holds for every node you reach by following neighbours.
• Cycles are expected. The graph is not a tree. You must detect a node you've already cloned and reuse that clone — otherwise you loop forever.
• Shared neighbours map to one clone. If two nodes both link to C, both of their clones must point to the same clone of C, not two separate copies.
• Undirected back-edges. Because edges are bidirectional, you'll reach a node, then reach it again from its neighbour. The second visit must not produce a second clone.
• null returns null. An empty graph has no node to clone.
• Values are copied, structure is preserved. Same val on each node, same neighbour count per node, same connectivity. Don't worry about node ordering within a neighbors array — preserve the order you're given.