Clone Graph
Given a reference to a node in a connected undirected graph, return a deep copy of the whole graph.
Open on LeetCode ↗Intuition
A plain traversal would loop forever on cycles, and copying a node twice would break the structure. The fix is one map: original node → its clone. Before copying a node, check the map — if a clone already exists, reuse it. The map is simultaneously the visited-set and the wiring table that keeps every edge pointing at the right copy.
Cloning anything with cycles needs a map from original to copy, and the ordering rule is the entire problem: register the clone before recursing into neighbours. That's what turns infinite recursion into termination. The same discipline applies to deep-copying any cyclic object graph.
Approach
Why naive copy fails
Recursively copying neighbors with no memory loops forever on any cycle (A→B→A→…), and even without cycles a node reachable by two paths would be duplicated.
Map originals to clones
Keep seen[original] = clone. On visiting a node: if it is in the map, return the existing clone. Otherwise create the clone first, register it, then fill its neighbor list recursively — registering before recursing is what breaks cycles.
DFS or BFS both work
The traversal order does not matter; only the map does. DFS is shorter; BFS avoids deep recursion on long chains.
Solution & live demo
Common pitfalls
Registering the clone after recursing
copy = Node(n.val) copy.neighbors = [dfs(nb) for nb in n.neighbors] seen[n] = copy
copy = Node(n.val) seen[n] = copy # register BEFORE recursing copy.neighbors = [dfs(nb) for nb in n.neighbors]
In any graph with a cycle, a neighbour eventually recurses back to a node still being built. If it isn't in the map yet, the lookup misses, a second clone is created, and the recursion never bottoms out. Registering first makes the in-progress clone visible to its own descendants.
Keying the map by node value
seen = {}
if n.val in seen: return seen[n.val]if n in seen: return seen[n]
Values are not guaranteed unique in the general case, and two distinct nodes sharing a value would collapse into one clone. Identity is what's being cloned.
Returning a shallow copy of the neighbour list
copy.neighbors = n.neighbors
copy.neighbors = [dfs(nb) for nb in n.neighbors]
That points the clone at the original nodes, so the two graphs stay entangled and mutating one affects the other. Every neighbour reference must be replaced by its clone.
Edge cases
Return null immediately.
Clone made, empty neighbor list, no recursion.
Clone registered in the map before recursing, so the cycle hits the map and stops.