Clone Graph

Problem

You’re 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 whole graph: a brand-new set of nodes with the same values and the same 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 meaningful “brute force” here — the trap is copying carelessly. If you recurse into every neighbor without remembering what you’ve already cloned, a cycle (1–2–3–4–1) makes you clone node 1 again when you follow 4’s edge back to it, then clone 2 again, forever. The whole problem is the visited-map bookkeeping, so we go straight to the two standard traversals.

Approach 2 — DFS with a clone map

The insight: map each original node to its clone the instant you create it — before recursing into neighbors. Then a cycle that leads back to an already-created node 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 []


class Solution:
    def cloneGraph(self, 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

The insight: same map trick, but visit level by level with a queue. Create a node’s clone when you first encounter it (either as the source you pop or as a neighbor you discover), and stitch edges as you process each popped node. Iterative BFS avoids Python’s recursion-depth limit — preferred when the graph could be deep/large, whereas DFS is often shorter to write for small inputs.

from collections import deque


class Solution:
    def cloneGraph(self, 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 do double duty as original → copy: check-or-create before you follow an edge. This single idea underlies DFS and BFS versions alike — pick BFS (queue) when recursion depth is a worry, DFS (recursion) when brevity wins.