Clone Graph
Deep-copy a graph with cycles — where a hash map stops being an optimisation and becomes the only thing that terminates
Problem Statement
Given a reference to a node in a connected undirected graph, return a deep copy: entirely new nodes, with the same values and the same connections.
Input: adjacency = [[2,4], [1,3], [2,4], [1,3]]
1 ---- 2
| |
4 ---- 3
Output: an identical graph made of entirely new nodesEach node holds a value and a list of neighbours.
Intuition
The obvious recursion — copy this node, then copy each neighbour — never terminates.
clone(1) → clone(2) → clone(1) → clone(2) → ...Undirected edges mean every connection is a two-step cycle. This is the hazard the graphs page warns about, but here the fix must do more than record visits.
The insight
Keep a map from original node → its copy.
It does two jobs at once, and that dual role is what makes this problem worth doing:
- Termination. A node already in the map has been handled. Return its copy and stop.
- Identity. Node 2's copy must point at the same copy of node 1 that node 4's copy points at — not a second copy holding the same value.
A plain visited set solves only the first. You would stop looping and still produce a broken graph, because nothing would let you find the copy you already made.
That second point is the real lesson. Copying a tree needs no map — each node has one parent, so no copy is ever needed twice. In a graph, several neighbours reach the same node, and they must all end up pointing at one shared copy.
Approach
Keep a map: original node → cloned node
Start it empty.
If the node is already in the map, return the stored copy
This is the base case. It terminates the recursion and guarantees shared identity.
Create the copy and put it in the map before recursing
This ordering is the whole solution. Registering the copy first means that when a neighbour recurses back into this node, the copy already exists.
Register the copy before recursing, not after
WRONG RIGHT
copy = new Node(node.val) copy = new Node(node.val)
for n in node.neighbours: seen[node] = copy ← first
copy.neighbours.append(...) for n in node.neighbours:
seen[node] = copy ← too late copy.neighbours.append(...)In the wrong version, node 1 recurses into node 2 before recording itself. Node 2 then looks up node 1, finds nothing, and creates a second copy — which recurses again. Infinite loop, one stack overflow.
The map entry must exist before any neighbour can ask about it.
Solution
class Node:
def __init__(self, val: int = 0, neighbors: list["Node"] | None = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph(node: Node | None) -> Node | None:
"""Deep-copy a connected undirected graph.
The map does double duty: it stops the recursion looping, and it
guarantees every reference to a node resolves to one shared copy.
"""
if node is None:
return None
seen: dict[Node, Node] = {}
def clone(original: Node) -> Node:
if original in seen:
return seen[original]
copy = Node(original.val)
seen[original] = copy # register BEFORE recursing
for neighbor in original.neighbors:
copy.neighbors.append(clone(neighbor))
return copy
return clone(node)The map is keyed by the node object, not its value. Python hashes objects by identity here, which is what makes two distinct nodes holding the same number map to different copies.
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V)
Time — each node is copied once (V) and each edge is walked once from each end (E). The map lookup is O(1).
Space — the map holds one entry per node, plus the recursion stack, which can reach V frames on a long chain. A BFS version with an explicit queue removes the stack-depth risk.
Edge Cases
Related Problems
- Number of Islands — traversal where a visited set is sufficient
- Two Sum — the hash map in its simplest role
- Graphs — why cycles make a memory mandatory