133. Clone GraphMedium

Analogy BFS Viz DFS Code Pitfalls Related

133. Clone Graph

MediumGraphBFSDFSHash Map·FacebookAmazon·⚡ Frequent

Given a reference to a node in a connected, undirected graph, return a deep copy of the graph. Each node has an integer value and a list of neighbors. Node values are unique from 1 to n.

0 ≤ number of nodes ≤ 100
1 ≤ Node.val ≤ 100, unique
No duplicate edges, no self-loops

Example

adjList[[2,4],[1,3],[2,4],[3,1]]

Output[[2,4],[1,3],[2,4],[3,1]]

Deep copy of a 4-node cycle graph.

Real-world analogy: Copying a city road network

🗺️ Road Network Duplicate: Imagine you're a city planner with a map of roads between intersections. You need to produce an exact duplicate map — same intersections, same connections — but on a separate sheet of paper.

The challenge: roads form cycles. If you just follow every road naively, you'll loop forever. The solution is a directory (the oldToNew map) — "intersection 3 on the original map corresponds to intersection 3* on the copy."

BFS strategy: Start at intersection 1. Clone it, write it in the directory. Enqueue it. Pop intersection 1, look at every road leaving it. For each road's destination — if not yet in the directory, clone it and enqueue it. Then draw the road on the copy. Repeat. When the queue empties, every intersection is cloned and every road is drawn.

Key insight: clone when you first see a node

The map lookup if nei not in oldToNew ensures each node is cloned exactly once. Even if three different paths lead to node 5, only the first creates the clone — subsequent visits just retrieve it from the map. This handles all cycles automatically.

Algorithm — BFS

Clone root, add to map, enqueue root.
While queue not empty:
  cur = dequeue
  For each neighbor nei of cur:
    If nei not in map → clone nei, enqueue nei
    Add clone(nei) to clone(cur).neighbors
Return map[root]

Approach	Time	Space	Notes
DFS (recursive)	O(V+E)	O(V)	Elegant; call stack up to V deep
BFS (queue) ✓	O(V+E)	O(V)	Iterative; no stack overflow risk

Visualizer — BFS Clone

Left = original graph · Right = cloned graph being built
● Orange = active node · ● Amber = in queue or neighbor being checked · ● Green = cloned

oldToNew MAP

(empty)

BFS QUEUE

(empty)

BFS CLONE—

Press ▶ or step forward to begin.

✓

—

SpacePlay/Pause ←→Step RReset F Fullscreen

Executing Code

def cloneGraph(self, node):

    if not node: return None

    oldToNew = {}; oldToNew[node] = Node(node.val)

    q = deque([node])

    while q:

        cur = q.popleft()

        for nei in cur.neighbors:

            if nei not in oldToNew:

                oldToNew[nei] = Node(nei.val)

                q.append(nei)

            oldToNew[cur].neighbors.append(oldToNew[nei])

    return oldToNew[node]

DFS Approach — O(V+E)

DFS is more concise. The map is checked at the top of each call — if already cloned, return immediately. This handles cycles without any explicit visited tracking.

dfs.py

def cloneGraph(self, node):
    oldToNew = {}

    def dfs(node):
        if node in oldToNew:
            return oldToNew[node]   # already cloned — reuse!
        copy = Node(node.val)
        oldToNew[node] = copy       # store BEFORE recursing (handles cycles)
        for nei in node.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy

    return dfs(node) if node else None

Common pitfalls

Forgetting to handle cycles

Without the map, DFS will recurse infinitely on any back-edge. Always store the clone in the map before recursing into neighbors — not after.

wrong vs correct

# WRONG: stores after recursion — infinite loop on cycles
copy = Node(node.val)
for nei in node.neighbors:          # ← recurses before storing!
    copy.neighbors.append(dfs(nei))
oldToNew[node] = copy               # too late

# CORRECT: stores before recursion
copy = Node(node.val)
oldToNew[node] = copy               # store first
for nei in node.neighbors:
    copy.neighbors.append(dfs(nei))

Cloning the same node multiple times

Two neighbors of different nodes may point to the same original node. Without the map, you'd create two separate clone objects — breaking the structure. The map guarantees a single clone per original node.

What to do next

Discussion

…

Loading comments…

LeetMotion