Clone Graph: A Clear Interview Walkthrough of Deep Copying with a Hash Map

"Clone Graph" asks you to deep-copy an undirected graph given one node. The real test is whether you notice that graphs can contain cycles, so a naive recursive copy will loop forever.

The one idea: map old nodes to new nodes

Keep a dictionary old_to_new. Before creating a copy of a node, check whether it already exists in the map. This single structure does two jobs: it is your visited set, and it lets you wire up neighbors to the correct copies.

DFS solution

def clone_graph(node):
    if node is None:
        return None
    old_to_new = {}

    def dfs(cur):
        if cur in old_to_new:
            return old_to_new[cur]
        copy = Node(cur.val)
        old_to_new[cur] = copy          # register BEFORE visiting neighbors
        for nb in cur.neighbors:
            copy.neighbors.append(dfs(nb))
        return copy

    return dfs(node)

Point out why you register the copy before recursing: if you waited until after, a cycle such as 1-2-1 would create a second copy of node 1.

BFS solution

from collections import deque

def clone_graph_bfs(node):
    if not node:
        return None
    old_to_new = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in old_to_new:
                old_to_new[nb] = Node(nb.val)
                q.append(nb)
            old_to_new[cur].neighbors.append(old_to_new[nb])
    return old_to_new[node]

Complexity and edge cases

Want help staying calm and structured during live coding rounds? this tool from Linkjob AI gives real-time hints during coding interviews.

Disclosure: written by the Linkjob AI team.