Return a deep copy of a connected undirected graph. Each node has a value and a list of neighbours.
1 --- 2| |4 --- 3 → an identical graph made of entirely new nodes
In plain English, we are given a reference to one node in a connected, undirected graph. We must return a "deep copy" of the graph. A deep copy means we cannot return the original nodes. We must create completely new Node objects for every node in the graph. Then we wire their neighbors arrays to point to the other new nodes, exactly mirroring the original graph's shape. The node values are unique and usually range from 1 to 100. One edge case is an empty graph (null input), which should return null.
The graph has cycles, so a naive recursive copy would loop forever: copying node 1 needs node 2, which needs node 1 again.
Nodes are shared. Node 3 is a neighbour of both 2 and 4, and it must be copied once, with both copies pointing at the same new node. Copy it twice and the shape is wrong.
Both are solved by the same thing: a map from each original node to its copy.
Before copying a node, check the map. If it is there, you have already made it — return the existing copy. That is what stops the infinite loop and what keeps shared nodes shared.
This is 4.9.5 Copy List with Random Pointer on a graph. Same map, same reason, different traversal. Seeing them as one problem is the point.
Think of building a precise replica of a tangled Lego model. You pick up a piece, look at what's attached to it, and start building. But wait—if you just blindly build whatever is attached, you'll hit a piece that connects right back to your starting piece. If you build another starting piece, you've ruined the shape. And you'll keep building forever in an endless loop! To solve this, you keep a "checklist" (our hash map). Every time you mold a new plastic piece, you write down: "Original Piece A -> New Piece A". Before you build anything, you check the list. If it's on the list, you just grab the one you already made and snap it on.
A naive approach would be standard recursion: copy the current node, then recursively copy all its neighbors and append them. Why does this fail? Because graphs have cycles. Node 1 connects to Node 2, and Node 2 connects back to Node 1. The naive recursion would try to copy Node 1, which copies Node 2, which copies Node 1, which copies Node 2, resulting in an infinite loop (a StackOverflowError). Even in a Directed Acyclic Graph (DAG) with no cycles, a naive approach would duplicate shared nodes. If Node A and Node B both point to Node C, the naive approach creates two separate Node C's. The map prevents both infinite loops and unintended duplication.
class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: # (1) return None old_to_new = {} # (2) def dfs(cur): # (3) if cur in old_to_new: # (4) return old_to_new[cur] # already copied — stops the cycle copy = Node(cur.val) # (5) old_to_new[cur] = copy # (6) register BEFORE recursing for nei in cur.neighbors: # (7) copy.neighbors.append(dfs(nei)) return copy # (8) return dfs(node) # (9)
ts
function cloneGraph(node: GNode | null): GNode | null { if (!node) return null; // (1) const map = new Map<GNode, GNode>(); // (2) function dfs(cur: GNode): GNode { // (3) const existing = map.get(cur); if (existing) return existing; // (4) const copy = new GNode(cur.val); // (5) map.set(cur, copy); // (6) for (const nei of cur.neighbors) { // (7) copy.neighbors.push(dfs(nei)); } return copy; // (8) } return dfs(node); // (9)}
Register the copy in the map before recursing into the neighbours. This is the line that matters.
If you registered it afterwards, then copying node 1 would recurse into node 2, which would recurse back into node 1 — still absent from the map — and the recursion would never end. Registering first means the cycle comes back, finds the entry, and returns immediately.
The copy is created empty and filled in during the recursion. At the moment it goes into the map it has no neighbours yet, and that is fine — by the time the outermost call returns, every neighbour list has been filled.
Objects as keys, compared by identity. Exactly right here: two different nodes with the same value must stay different. Note this is the opposite of 4.4.4 Group Anagrams, where identity comparison was the bug. Ask which one you want: identity when tracking specific objects, value when grouping equal ones.
(3) dfs(cur) returns the copy of cur, making it if needed.
(4) Already copied? Return that copy. This line does two jobs. It stops the same node being copied twice, and it stops the walk going round a cycle forever, because a node we come back to is already in the map.
(5) Make a copy of this node, with no neighbours yet.
(6) Record it in the map before visiting any neighbour. If a neighbour leads back to this node, line (4) must already find the copy. Recording it after the loop would let the walk circle forever.
(7) Copy each neighbour, and link this copy to the neighbour's copy.
(8) Return the finished copy.
(9) Start from the given node. The whole connected graph gets copied, because every node is reachable from it.
from collections import dequedef cloneGraph(self, node): if not node: return None old_to_new = {node: Node(node.val)} queue = deque([node]) while queue: cur = queue.popleft() for nei in cur.neighbors: if nei not in old_to_new: old_to_new[nei] = Node(nei.val) # create on first sight queue.append(nei) old_to_new[cur].neighbors.append(old_to_new[nei]) return old_to_new[node]
Same logic, no recursion, so no stack depth limit. Note the neighbour link is added outside the if — the copy must be linked every time the edge is seen, even though the node is only created once.
Use BFS when the graph could be large enough to overflow the stack.
O(V + E) time — each node is created once and each edge is walked once. In an undirected graph each edge is walked twice, once from each end, which is still O(E). To derive this: the dfs is called for every node, and inside it, we iterate over its neighbors. This means we process every node (O(V)) and we iterate over every edge connection (O(E)). Since O(V) hash map lookups and insertions are O(1), the total time scales linearly with the size of the graph.
O(V) space for the map, plus O(V) for the recursion or queue. The map stores exactly V entries. The call stack (for DFS) will go as deep as the longest path in the graph, which in the worst case (a straight line graph) is V. Thus, total auxiliary space is strictly bounded by O(V).
Empty Graph (Null input): Handled elegantly by the if not node: check at the very beginning.
Single Node Graph (No edges): Works flawlessly. The loop for nei in cur.neighbors: will simply not execute, returning the copy immediately.
Disconnected Graph: The problem explicitly states the graph is connected. But what if it wasn't? The current DFS only clones the connected component of the input node. To clone a fully disconnected graph, we would need a list of all nodes and iterate through them, calling dfs on any node not yet in our old_to_new map.
Copy List with Random Pointer — the same map on a linked list. 4.9.5.
Deep copy in real code — structuredClone, Python's deepcopy, and any serialiser that supports shared references all keep an identity map for exactly this reason. Without it, a cyclic object graph crashes the copier, which is why JSON.stringify throws on a cycle.
Clone a binary tree with random pointers — same idea again.
The rule: to copy any structure with cycles or shared nodes, keep a map from original to copy and register each copy before following its links.
"Why do you need the map?" Two reasons — it terminates the cycles, and it keeps shared nodes shared. Say both; most candidates give only one.
"Why register the copy before recursing?" Otherwise a cycle re-enters a node that is not yet in the map and recurses forever.
"What are the map keys?" The original node objects, compared by identity.
"What if the graph is disconnected?" The problem promises it is connected. If not, you would loop over all nodes and clone from each unvisited one — exactly the outer loop of 4.20.1.
"BFS or DFS?" Either. BFS avoids the stack depth risk.
One thing to volunteer: connect it to JSON.stringify throwing on circular references. It shows the problem is a real one that real tools have to solve.