Clone Graph: Copy Nodes Without Falling Into the Cycle

"Clone Graph" is the moment an interviewer finds out whether you have only cloned trees. A tree copy is a recursion with a null base case. An undirected graph has cycles; recurse without a map and you infinite-loop, or you emit two clones of the same node and the copy is a different shape. The problem is LeetCode 133, and it is a Graph BFS (or DFS) pattern with an identity table.

The Problem

Each node has a val and a list of neighbors. The graph is undirected, connected from the given node, and nodes have unique values in the usual statement. Return a deep copy: new node objects, same connectivity, no shared references with the original.

Input:  1 -- 2
        |    |
        4 -- 3
Output: a new 1--2--3--4 cycle, disjoint in memory.

Recognizing the Graph Traversal Pattern

You must visit every node and every edge once, which is ordinary BFS/DFS, and you must not create a second clone when you see a node again via another edge. That second requirement is the map: original -> clone. First time you see a node, allocate the clone and record it; every later time, reuse it when wiring neighbors. Trees hide this because there is only one parent pointer inbound; graphs do not.

Say the map out loud before you code. Interviewers are listening for "I need identity, not just a traversal."

The Approach

BFS from the start node. Seed the queue and the map with the clone of the start. For each dequeued original, iterate neighbors: if a neighbor is not in the map, clone it, map it, enqueue it; then append map[neighbor] to map[current].neighbors. DFS is the same map with a recursive clone(node) that returns map[node] after creating it and walking neighbors.

Do not copy neighbor lists by value (clone.neighbors = node.neighbors). That aliases the original graph and fails any interviewer who checks is.

Empty input: return None. Single node with no neighbors: one new node, empty list. A self-loop (rare in the stock prompt, fair as a follow-up): the map already contains the node, so you append the clone to its own neighbors — which is what you want.

Python Solution

from collections import deque

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

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

    clones = {node: Node(node.val)}
    q = deque([node])

    while q:
        cur = q.popleft()
        for nbr in cur.neighbors:
            if nbr not in clones:
                clones[nbr] = Node(nbr.val)
                q.append(nbr)
            clones[cur].neighbors.append(clones[nbr])

    return clones[node]

DFS variant: the recursive function is four lines once the map is in the closure — create, store, then clone.neighbors = [dfs(n) for n in node.neighbors]. Both are O(V+E). Prefer BFS if you have already used recursion on a previous question and the interviewer looks bored; prefer DFS if you want fewer moving parts.

Complexity

• Time: O(V + E) — each node enqueued once, each edge examined once (twice in an undirected adjacency list, still linear)
• Space: O(V) for the map and the queue (or the call stack)

Interview Tips and Follow-Ups

• They may ask you to clone a disconnected graph: then you need the full node list, not a single source. Say you would iterate all nodes as potential BFS starts, skipping those already in the map.
• Random pointer lists (Copy List with Random Pointer) are the same map idea on a different shape — mention it if you finish early.
• Do not hash on val unless the problem guarantees uniqueness and you say so; hashing on the node object is the general solution.
• A common bug: creating the neighbor clone but forgetting to enqueue it, so its edges never copy. Walk a square on the whiteboard and show each map insertion.

This is Graph BFS with an identity table — the same muscle as "copy with random pointer" and the setup for any "transform a cyclic structure." More graph problems live in the Technical Interview category.