Clone Graph, traced one call at a time

dfs(old) returns the copy of old. If the map already has one it hands it back; otherwise it makes the copy, registers it in the map first, then links in a copy of each neighbour. Registering first is what lets a cycle come back around and find the copy instead of looping forever.

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Recursion tree

Every neighbour visit is a call; dashed blue ones end at the map lookup

not called yet running now paused, waiting on a child call made a new copy found in the map, reused

Call stack

Top frame runs; the rest are paused

Graphs

Same layout on both sides; primes (2′) are copies

original (read only)
clone (being built)

clones original → copy

copies' neighbour lists filled one append at a time

dfs running on this node copy in progress (on the stack) finished edge being followed →one append in the clone

Keyboard: ← → step, Space play or pause. Paste any connected undirected graph in LeetCode's adjList format, up to 8 nodes. Every edge is visited twice, once from each end; the second visit is always a map hit.