Clone Graph

Signal

"Deep copy a graph" means traversing it — but a graph can have cycles, so a plain traversal that recurses into neighbors will loop forever unless you remember what you've already cloned. The trigger: DFS/BFS traversal plus a hash map from original node to its clone, checked before you recurse.

Approach

Walk the graph (DFS or BFS) starting from the given node. The first time you see an original node, create its clone immediately and store the mapping original -> clone before recursing into its neighbors — that way, if a cycle leads back to a node you're still processing, the lookup finds the already-created clone instead of recursing again.

Skeleton

cloned = {}  # original node -> clone

def clone(node):
    if node in cloned:
        return cloned[node]
    copy = Node(node.val)
    cloned[node] = copy
    for neighbor in node.neighbors:
        copy.neighbors.append(clone(neighbor))
    return copy

return clone(start_node)

Solution

class Node:
    def __init__(self, val: int = 0, neighbors: list['Node'] | None = None):
        self.val = val
        self.neighbors = neighbors or []


def clone_graph(node: 'Node | None') -> 'Node | None':
    if node is None:
        return None

    cloned: dict[Node, Node] = {}

    def clone(n: Node) -> Node:
        if n in cloned:
            return cloned[n]
        copy = Node(n.val)
        cloned[n] = copy
        copy.neighbors = [clone(neighbor) for neighbor in n.neighbors]
        return copy

    return clone(node)

Complexity

O(V + E) time — every node is cloned once and every edge is traversed once. O(V) space for the cloned map plus recursion stack depth.

Pitfalls

• Creating the clone's neighbor list before registering the clone in the map causes infinite recursion on any cycle — register the empty/new clone in cloned first, then fill in neighbors.
• Using the node's val as the map key instead of the node object itself breaks silently if the graph has duplicate values.
• Iterative BFS needs the same "create-and-register-before-expanding" order — the map, not the traversal style, is what prevents infinite loops.