Clone Graph

Problem

You are given a reference to a node in a connected, undirected graph. Each node holds an integer val and a list of its neighbors. Return a deep copy of the graph: a new set of nodes with the same values and connectivity, sharing no objects with the original.

The graph is described for testing with an adjacency list (1-indexed), but your function receives only the single starting node. Values are unique and, by convention, the i-th node has val = i. An empty graph (a None start node) must return None.

Node definition:

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

Examples

• adjList = [[2,4],[1,3],[2,4],[1,3]] → a 4-node cycle 1–2–3–4–1, deep-copied. Node 1’s clone links to clones of 2 and 4, and none of the returned objects are the originals.
• adjList = [[]] → one node with value 1 and no neighbors → a single fresh isolated node.
• adjList = [] → empty graph → return None.

Constraints

• Number of nodes is in [0, 100].
• 1 <= Node.val <= 100, all values unique.
• The graph is connected and undirected (every edge appears in both endpoints’ lists); no self-loops, no repeated edges.

Think about it first

TL;DR

Traverse the graph (DFS or BFS) while keeping an original → clone hash map so each node is copied once — O(V + E) time, O(V) space.

Approach 1 — Why the naive copy fails

There is no useful brute force here; the failure mode is copying without tracking what you have already copied. If you recurse into every neighbor with no memory of prior clones, a cycle (1–2–3–4–1) clones node 1 again when you follow 4’s edge back to it, then clones 2 again, and never terminates. The problem reduces to the visited-map bookkeeping, so we go straight to the two standard traversals.

The test graph is a 4-node cycle:

graph LR
    1 --- 2
    2 --- 3
    3 --- 4
    4 --- 1

Approach 2 — DFS with a clone map

Map each original node to its clone the instant you create it, before recursing into neighbors. A cycle that leads back to an already-created node then finds it in the map and stops instead of cloning it again. The map serves as both the copy registry and the visited set.

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


def cloneGraph(node: 'Node') -> 'Node':
    if node is None:
        return None
    clones: dict['Node', 'Node'] = {}

    def dfs(cur: 'Node') -> 'Node':
        if cur in clones:
            return clones[cur]
        copy = Node(cur.val)
        clones[cur] = copy          # record BEFORE recursing
        for nei in cur.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy

    return dfs(node)

Walkthrough (adjList = [[2,4],[1,3],[2,4],[1,3]], start at node 1):

• dfs(1): create clone 1’, store {1:1'}. Neighbors of 1 are 2, 4.
• dfs(2): create 2’, store {1:1',2:2'}. Neighbors 1, 3. dfs(1) returns 1’ from the map. dfs(3) creates 3’, whose neighbors 2 (map hit → 2’) and 4 (dfs(4) creates 4’, neighbors 1→1’, 3→3’).
• Every back-edge to an already-cloned node is a map lookup, so recursion terminates. Result: a fresh 4-cycle.

Complexity: each node is created once and each edge is walked once → O(V + E) time. The map plus recursion stack are O(V) space.

Approach 3 — BFS with a clone map

Same map, but visit level by level with a queue. Create a node’s clone when you first encounter it (either as the node you pop or as a neighbor you discover), and wire edges as you process each popped node. Iterative BFS avoids Python’s recursion-depth limit, so it is the safer choice when the graph could be deep or large; DFS is usually shorter to write.

from collections import deque


def cloneGraph(node: 'Node') -> 'Node':
    if node is None:
        return None
    clones = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        cur = queue.popleft()
        for nei in cur.neighbors:
            if nei not in clones:
                clones[nei] = Node(nei.val)   # first sighting → clone it
                queue.append(nei)
            clones[cur].neighbors.append(clones[nei])

    return clones[node]

Walkthrough (same 4-cycle): seed clones={1:1'}, queue [1]. Pop 1: neighbor 2 unseen → make 2’, enqueue; wire 1’→2’. Neighbor 4 unseen → make 4’, enqueue; wire 1’→4’. Pop 2: neighbor 1 seen → wire 2’→1’; neighbor 3 unseen → make 3’, wire 2’→3’. Continue until the queue empties; every edge wired exactly once.

Complexity: O(V + E) time, O(V) space for the map and queue — identical to DFS.

Common pitfalls

• Recording the clone after recursing into neighbors instead of before — a cycle then re-enters the node and infinite-loops.
• Using val as the map key. It happens to be unique here, but keying on the node object is the habit that survives problems with duplicate values.
• Forgetting the node is None guard for the empty-graph test.
• Since the graph is undirected, each edge is stored on both endpoints — you’ll naturally add both directions; don’t try to “dedupe” and drop one.

Pattern takeaway

To copy or traverse a graph that may contain cycles, carry a visited structure keyed on the node itself. When the task is cloning, let the visited map double as original → copy: check-or-create before you follow an edge. The same idea drives both the DFS and BFS versions. Pick BFS (queue) when recursion depth is a concern, DFS (recursion) for shorter code.