You get a reference to one node in a connected, undirected graph and have to return a deep copy: a brand-new set of nodes wired together identically, sharing nothing with the original. That is LeetCode 133, and it earns its place in onsites because the traversal you would reach for on a tree quietly falls apart the moment the graph contains a cycle.
The node looks like this:
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors or []Undirected edges mean every connection is stored twice. If node 1 lists 2 as a neighbor, then 2 lists 1 right back. So even the smallest interesting input, two nodes joined by an edge, already contains a cycle. Walk it the way you would walk a binary tree and you never stop.
Why the obvious recursion runs forever
Say you write the natural thing: make a copy of the current node, then for each neighbor, recurse and attach the result. Start at node 1 and copy it. Recurse into node 2 and copy that. Node 2’s neighbor list still points back at node 1, so you recurse into 1 and copy it all over again, then into 2 again, and around you go. Nothing tells the recursion you have already been somewhere, so it spirals. And in the rare shape where it did terminate, you would have minted a fresh copy of node 1 on every visit, so the copy would not even match the original.
Both problems have one fix. Keep a map from each original node to its clone. The first time you meet a node you build its clone and record it. Every time after that you hand back the clone you already made. The map is doing double duty: it dedupes shared neighbors, and it marks nodes as visited so cycles terminate.
Register the clone before you recurse
class Solution:
def cloneGraph(self, node):
if not node:
return None
clones = {}
def dfs(cur):
if cur in clones:
return clones[cur]
copy = Node(cur.val)
clones[cur] = copy # record it first
for nb in cur.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)The one line that matters is clones[cur] = copy sitting above the loop, not below it. Put the map insertion after the neighbor loop and the code looks almost identical, passes on a straight-line graph, and hangs forever the first time a neighbor points back at a node still on the call stack. That node never got recorded, so the base case never fires. Interviewers who know the problem watch for exactly this ordering, and swapping those two lines is the most common way an otherwise strong candidate still fails the run.
Everything else is bookkeeping. You copy the value, then build the clone’s neighbor list by resolving each original neighbor to its clone, creating that clone on first sight.
The BFS version
Same map, no recursion. A queue holds original nodes whose neighbor wiring you still owe. You clone the entry node up front so the map is never empty when the loop starts.
from collections import deque
class Solution:
def cloneGraph(self, node):
if not node:
return None
clones = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nb in cur.neighbors:
if nb not in clones:
clones[nb] = Node(nb.val)
q.append(nb)
clones[cur].neighbors.append(clones[nb])
return clones[node]A clone gets created when its node is first discovered as a neighbor of something else, and that clone’s own neighbors get filled in later when it comes off the queue. Splitting discovery from wiring is what keeps each node and each edge touched once.
Both versions run in O(N + M) time for N nodes and M edges, since you visit every node once and walk every edge once. Space is O(N): the map holds one entry per node, and on top of that DFS carries a call stack down to the graph’s depth while BFS carries a queue up to its width.
| Approach | Extra space beyond the clone map | Main risk | When to reach for it |
|---|---|---|---|
| Recursive DFS | Call stack, up to graph depth, O(N) | Stack overflow on a long chain of nodes | Fastest to write correctly under time pressure |
| Iterative BFS (queue) | Queue, up to graph width, O(N) | None significant at interview input sizes | When you want no recursion, or the graph could be deep |
| Iterative DFS (explicit stack) | Stack, up to graph depth, O(N) | Easy to misorder discovery versus wiring | Rarely needed; mention it if asked to drop recursion |
What actually identifies a node
LeetCode promises node values are unique and run 1 to 100, so you can get away with keying the map on cur.val instead of the node object. It works here and it is a fine thing to say out loud. But lean on it and a sharp interviewer asks the obvious follow-up: what if two nodes share a value? A val-keyed map collapses them into one and your copy comes out wrong. Keying on the node’s identity, the object reference, which is what a Python dict does by default with these objects, sidesteps the whole question and generalizes to graphs where values repeat. In Java you would use an IdentityHashMap or the node reference itself; in C++ an unordered_map<Node*, Node*>.
The follow-ups worth rehearsing
The disconnected case trips people up. This problem hands you a single node and guarantees the graph is connected, so one traversal reaches everything. Drop that guarantee and a single entry point no longer sees the other components. You would need the full list of nodes and a loop that starts a fresh traversal from any node not yet in the map, reusing the same clone map across all of them so shared structure still lines up.
A directed graph changes nothing about the algorithm; the map still terminates cycles and dedupes. What changes is that reaching B from A no longer implies you can reach A from B, which again pushes you toward iterating over all nodes when connectivity is not promised.
If the theme is deep copy, the sibling problem is Copy List with Random Pointer, LeetCode 138. A linked list where each node also points at an arbitrary other node is the same puzzle in a thinner costume: you cannot set the random pointers on the first pass because their targets may not exist yet, so you build an old-to-new map first and wire the pointers second. Spotting that 138 and 133 are the same idea reads as experience rather than memorization.
That old-to-new map is the thing to walk out with. Any time you copy a structure that can reference itself, a graph, a list with tangled pointers, an object graph headed for serialization, the move is the same. Create the new object on first contact, record the mapping, resolve every reference through it. The traversal order barely matters. The map is the whole game.
Drill the patterns next:
