Clone a Graph: Deep Copy with DFS and BFS

Clone a Graph (LeetCode 133) is a foundational graph problem that tests your understanding of deep copy vs shallow copy, cycle handling in graphs, and the difference between BFS and DFS traversal with memoization. It appears at Google and Facebook interviews.

Problem

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a value and a list of neighbors.

DFS Solution

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph_dfs(node: Node) -> Node:
    """
    DFS with memoization (old_node -> cloned_node mapping).
    The memo dict handles cycles: if we've already cloned a node,
    return the existing clone instead of recursing infinitely.
    Time: O(V + E), Space: O(V)
    """
    if node is None:
        return None

    memo = {}  # Maps original node -> cloned node

    def dfs(original):
        if original in memo:
            return memo[original]  # Return already-cloned node (handles cycles)

        clone = Node(original.val)
        memo[original] = clone  # Register BEFORE recursing to handle cycles

        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))

        return clone

    return dfs(node)

BFS Solution

from collections import deque

def clone_graph_bfs(node: Node) -> Node:
    """
    BFS-based deep copy. More iterative, avoids Python's recursion limit.
    """
    if node is None:
        return None

    memo = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        original = queue.popleft()

        for neighbor in original.neighbors:
            if neighbor not in memo:
                memo[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            # Connect the clone's neighbor
            memo[original].neighbors.append(memo[neighbor])

    return memo[node]

Why the Memo Dict Goes Before Recursion

This ordering is critical:

clone = Node(original.val)
memo[original] = clone  # ← MUST happen before recursing into neighbors

for neighbor in original.neighbors:
    clone.neighbors.append(dfs(neighbor))  # dfs may return to this node via cycle

If you register after recursing, a cycle (A → B → A) would cause infinite recursion: A’s clone isn’t in memo when B tries to clone A again.

Testing the Clone

def verify_deep_copy(original: Node, cloned: Node) -> bool:
    """Verify clone is a true deep copy: same structure, different objects."""
    visited = set()
    stack = [(original, cloned)]

    while stack:
        orig, clone = stack.pop()
        if id(orig) == id(clone):
            return False  # Same object — not a deep copy!
        if orig.val != clone.val:
            return False  # Different values
        if len(orig.neighbors) != len(clone.neighbors):
            return False

        if id(orig) in visited:
            continue
        visited.add(id(orig))

        for o_neighbor, c_neighbor in zip(orig.neighbors, clone.neighbors):
            stack.append((o_neighbor, c_neighbor))

    return True

Generalizing: Deep Copy Patterns

The clone graph pattern applies to any object graph with cycles:

Cloning a linked list with random pointers (LeetCode 138)
Copying directory trees with symlinks (cycles)
Serializing graph state in game engines

The universal pattern: memo = {} where you register the new object immediately before recursing into references.