Clone Graph: Deep-Copying a Graph Without Looping Forever
How to deep-copy an undirected graph with a BFS and a hash map — intuition, JavaScript code, a worked walkthrough, complexity, and the cycle traps to avoid.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Copying a linked list is easy: walk it, allocate a new node per step, done. Copying a graph is where people fall off a cliff — because graphs have cycles, and a naive copy that follows edges will happily loop back to a node it already copied and start again, forever.
Clone Graph is the problem that forces you to internalize the one tool that tames cycles in every graph traversal: a map from original node to its clone. That map is the difference between "visit each node once" and "recurse until the stack blows up." Get it here and Course Schedule, Number of Islands, and Word Ladder all stop being scary.
The problem
You're given a reference to one node in a connected, undirected graph. Every node holds an integer val and a list of neighbors. Return a deep copy of the whole graph — a brand-new set of nodes with the same values and the same connections, sharing zero references with the original.
Input (adjacency list):
1 —— 2
| |
4 —— 3
adjList = { 1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3] }
Output: a new graph, identical shape, where clone(1).neighbors
are clone(2) and clone(4) — never the originals.Two facts in that statement drive everything:
- The graph is undirected, so every edge shows up twice (
1lists2, and2lists1). You will reach the same node from multiple directions. - The graph can have cycles.
1 → 2 → 3 → 4 → 1is a loop. Any copy strategy that blindly follows neighbors has to know when it's already been somewhere.
The brute force baseline
The instinct is a plain recursive copy: make a clone of the current node, then recurse into each neighbor and attach their clones.
function cloneGraph(node) {
if (!node) return null;
const copy = new Node(node.val);
for (const nbr of node.neighbors) {
copy.neighbors.push(cloneGraph(nbr)); // no memory of what's cloned
}
return copy;
}This never terminates. Start at 1, recurse into 2, then into 3, then 4, then 4's neighbor 1 — which recurses into 2 again, and around the cycle you go. Even without a cycle, the undirected duplicate edges (1↔2) send you bouncing between two nodes indefinitely. The function has no memory of which originals it has already cloned, so it re-clones them endlessly. It's not slow — it's a stack overflow.
The key insight: one clone per original, remembered in a map
The fix is to guarantee exactly one clone per original node, and to look that clone up instead of re-creating it. A hash map keyed by the original node reference does both jobs:
visited.has(original)answers "have I already cloned this?" in O(1). If yes, don't clone again — reuse.visited.get(original)hands back the existing clone so you can wire edges to it.
Keying by node reference (not by val) matters: two different nodes could share a value, and you need each tracked separately. Once every original maps to a stable clone, cycles resolve themselves — the second time you reach node 1, the map already holds clone(1), so you just link to it and move on.
With the map in place, a BFS visits each node once and wires its edges as it goes.
The optimal solution
This is the exact BFS the visualizer steps through — a queue for traversal, a visited map from original to clone, and the root cloned eagerly before the loop so the map is never empty.
var cloneGraph = function(root) {
if (!root) return null;
const q = [root];
const visited = new Map();
const cloneRoot = new Node(root.val);
visited.set(root, cloneRoot);
while (q.length) {
const curr = q.shift();
const cloneCurr = visited.get(curr);
for (const n of curr.neighbors) {
if (!visited.has(n)) {
visited.set(n, new Node(n.val)); // first sighting: clone + enqueue
q.push(n);
}
cloneCurr.neighbors.push(visited.get(n)); // wire clone → clone, always
}
}
return cloneRoot;
};The structure is worth reading carefully. Cloning a node and wiring its edges are separate concerns. A node gets cloned the first time it's ever seen as a neighbor (and enqueued so we later process its own neighbors). But the edge wiring — cloneCurr.neighbors.push(...) — runs on every neighbor, seen or not, because every original edge needs a matching clone edge. The if (!visited.has(n)) guard only protects the clone creation and enqueue, never the wiring.
Walkthrough
Trace a triangle where all three nodes connect to each other: adjList = { 1: [2, 3], 2: [1, 3], 3: [1, 2] }. Before the loop: cloneRoot = 1', visited = {1→1'}, q = [1].
| curr | neighbor n | in visited? | Map action | cloneCurr.neighbors after | queue after |
|---|---|---|---|---|---|
| 1 | 2 | no | clone 2', enqueue 2 | 1' → [2'] | [2] |
| 1 | 3 | no | clone 3', enqueue 3 | 1' → [2', 3'] | [2, 3] |
| 2 | 1 | yes | reuse 1' | 2' → [1'] | [3] |
| 2 | 3 | yes | reuse 3' | 2' → [1', 3'] | [3] |
| 3 | 1 | yes | reuse 1' | 3' → [1'] | [] |
| 3 | 2 | yes | reuse 2' | 3' → [1', 2'] | [] |
Notice the pattern: node 1 clones both its neighbors on first contact, but by the time we process 2 and 3, everything already lives in the map, so those rows are pure edge-wiring — no new clones. The queue drains to empty, we return 1', and the clone is a perfect mirror with three nodes and six directed edges, sharing no references with the original.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(V + E) | Each of V nodes is dequeued once; across all nodes we touch each of the E edges exactly once (twice total for undirected, still O(E)). |
| Space | O(V) | The visited map holds one entry per node, and the queue holds at most O(V) nodes. |
V is the node count, E the edge count. There's no hidden factor — the map lookup and insert are O(1) average case, so the traversal cost is linear in the size of the graph.
Common mistakes
- Skipping the wiring on already-visited neighbors. Putting
cloneCurr.neighbors.push(...)inside theif (!visited.has(n))block means back-edges and cycle-closing edges never get copied. The clone comes out with missing connections. Wiring runs for every neighbor; only cloning is guarded. - Keying the map by
valinstead of the node. If two nodes share a value, a value-keyed map collapses them into one clone and corrupts the copy. Key by the node object reference. - Cloning the root inside the loop. If you don't seed
visitedwith the root before thewhile, the first iteration re-clones it (or worse,visited.get(curr)returnsundefined). Clone the root eagerly, then enqueue. - Pushing original neighbors into the clone.
cloneCurr.neighbors.push(n)links your copy back to the original graph. It must bevisited.get(n)— always a clone reference. - Forgetting the empty input. A
nullroot should returnnull. Without the early guard,new Node(root.val)throws.
Where this pattern shows up next
The "traverse with a visited structure, do work per node" template is the backbone of graph problems:
- Max Area of Island — the same visited-tracking traversal, but accumulating a count instead of building clones.
- Find if Path Exists in Graph — BFS/DFS reachability, the simplest form of "visit each node once."
- All Paths From Source to Target — DFS on a DAG where backtracking replaces the visited set.
- Redundant Connection — cycle detection from the union-find angle, the complement to tracking visits in a map.
You can also step through Clone Graph interactively to watch the queue drain, the hash map fill, and each clone edge wire up, in BFS or DFS mode.
FAQ
Why does Clone Graph need a hash map at all?
Because the graph has cycles and undirected duplicate edges, you reach the same node from multiple directions. Without a map recording "original node → its clone," each arrival re-clones the node, and cycle edges send the traversal looping forever. The map guarantees exactly one clone per original and lets you reuse it in O(1), which is what makes the traversal terminate and stay linear.
Can I solve Clone Graph with DFS instead of BFS?
Yes — the visualizer offers both. DFS uses recursion (or an explicit stack) instead of a queue, but the core is identical: check the visited map, clone on first sight, and wire the clone's neighbors to other clones. Both are O(V + E) time. BFS uses queue space proportional to the graph's width; recursive DFS uses call-stack space proportional to its depth. Pick whichever you find easier to write correctly under pressure.
What is the time and space complexity of Clone Graph?
Time is O(V + E): every node is dequeued once, and every edge is examined once during neighbor iteration. Space is O(V) for the visited map (one entry per node) plus the queue or recursion stack, which also holds at most O(V) nodes. There's no O(V²) blow-up because the map turns every "have I seen this node?" question into a constant-time lookup.
Why clone the root before the loop instead of inside it?
Seeding visited with the root's clone before the while loop means the map is never empty when the loop starts, so visited.get(curr) always returns a valid clone to wire edges onto. If you cloned lazily inside the loop, the first dequeue would find no entry for the root and either crash or create a duplicate. Eager root cloning keeps the invariant "every enqueued node already has a clone in the map" true from the very first iteration.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.