MediumMake a deep copy of an undirected graph — every node and edge duplicated.
You are given a reference to a node in a connected undirected graph. Each node has a value and a list of its neighbors. Return a deep copy (clone) of the graph: a brand-new set of nodes that has the same values and the same connections, sharing nothing with the original.
Walkthrough
try:
adjList[i] lists the neighbours of node i+1 (undirected). n is read from the list length.
traverse with:
original (input)
clone (being built)
currneighbourcloned
1
function cloneGraph(node) {
2
if (!node) return null;
◄
3
const clones = new Map();
4
clones.set(node, new Node(node.val));
5
const queue = [node];
6
while (queue.length) {
7
const curr = queue.shift();
8
for (const nei of curr.neighbors) {
9
if (!clones.has(nei)) {
10
clones.set(nei, new Node(nei.val));
11
queue.push(nei);
12
}
13
clones.get(curr).neighbors.push(clones.get(nei));
14
}
15
}
16
return clones.get(node);
17
}
node = 1
step 0 / 33
queue (nodes still to process)
(empty)
line 2
Start node exists
node is not null, so we have a real graph to copy.
Intuition
The hard part is not copying values — it is copying the edges without getting stuck in cycles. If you blindly follow neighbours you will clone the same node again and again forever.
Keep a map from each ORIGINAL node to its NEW copy. Before you ever follow a node’s edges, put its copy in the map. That way every node is created exactly once.
Walk the graph (BFS with a queue, or DFS with recursion). For each node you visit, look at its neighbours: clone any neighbour you have not seen, then wire the copy’s edge to the neighbour’s copy.
Because the map is checked first, revisiting an already-cloned node just reuses its copy instead of making a new one — that is what tames the cycles.
The algorithm
01If the input node is null, return null.
02Create the start node’s copy and put original → copy in a map; seed the queue (BFS) with the start node.
03Pop a node. For each neighbour: if it is not in the map, clone it and enqueue it.
04Connect the current node’s copy to the neighbour’s copy (rebuilding the edge).
05Repeat until the queue is empty, then return the copy of the start node.
Reference implementations
1 · BFS — queue + map
Clone the start node, then process the queue: for each node, clone any unseen neighbour, enqueue it, and link the copies. This is the version animated above.
1
function cloneGraph(node) {
2
if (!node) return null;
3
const clones = new Map(); // original -> copy
4
clones.set(node, new Node(node.val));
5
const queue = [node];
6
while (queue.length) {
7
const curr = queue.shift();
8
for (const nei of curr.neighbors) {
9
if (!clones.has(nei)) {
10
clones.set(nei, new Node(nei.val));
11
queue.push(nei);
12
}
13
clones.get(curr).neighbors.push(clones.get(nei));
14
}
15
}
16
return clones.get(node);
17
}
2 · DFS — recursion + map
Recurse from the start node. Record a node’s copy in the map BEFORE recursing into its neighbours so cycles resolve to the existing copy instead of looping forever.
1
function cloneGraph(node) {
2
const clones = new Map(); // original -> copy
3
function dfs(curr) {
4
if (clones.has(curr)) return clones.get(curr);
5
const copy = new Node(curr.val);
6
clones.set(curr, copy); // record before recursing (handles cycles)
7
for (const nei of curr.neighbors) {
8
copy.neighbors.push(dfs(nei));
9
}
10
return copy;
11
}
12
return node ? dfs(node) : null;
13
}
Complexity
Time
O(V + E) — each node and edge is visited once.
Space
O(V) for the map and the queue (or recursion stack).