Clone Graph

Given a reference to a node in a connected graph, return a deep copy of the graph. Each node has a Val and a list of Neighbors.

Why this is worth learning

A deep copy preserves topology, sharing, cycles, and adjacency order while replacing every node identity. The map is not merely visited state: it is the correspondence between the two graphs.

Before coding: one-minute experiment

In a triangle A-B-C-A, why must A be entered in the clone map before recursively copying B?

Function signature

func CloneGraph(node *Node) *Node

Inputs / outputs

• node: a pointer to any node in the graph (may be nil).
• Return: the cloned node corresponding to node.

Example

1 -- 2
|  / |
3 -- 4
Output: a new graph with the same connections

Constraints

• 0 <= number of nodes <= 100_000
• node values are unique within the graph

Core idea (near-solution)

Recursively allocating along each child edge works on a rooted tree represented by child-only edges. General neighbor lists include shared targets and return edges; even a two-node undirected tree can revisit its parent. A visited boolean prevents looping yet still cannot answer which copied node a repeated edge should reference. Store original pointer→copy pointer instead, and publish a newly allocated copy in the map before following neighbors. Every later encounter reuses it. Preserve the neighbor list itself, including order, duplicate entries and self-loops; reducing it to a set would silently change the graph's contract.

Invariant: if a node exists in the map, its clone is already fully or partially constructed and must be reused.

Algorithm (step-by-step)

1. If node is nil, return nil.
2. Create copies := map[*Node]*Node.
3. DFS/BFS starting from node:
   • If the current node is not in copies, create its clone and store it.
   • For each neighbor:
     • If the neighbor is not in copies, create its clone and enqueue/recurse.
     • Append the neighbor's clone to the current clone's neighbor list.
4. Return copies[node].

Correctness sketch

On the first encounter with an original node, allocate exactly one clone and record it before exploring neighbors. Every later encounter returns that same clone, so cycles terminate and two references to one original remain two references to one clone. For every adjacency entry u->v, append the mapped clone of v to the clone of u in the original order. Induction over first discoveries constructs all reachable nodes; revisits preserve established identities. All allocated nodes are fresh, and no original field is written, so the result is disjoint from the source and preserves its entire reachable adjacency structure.

Trace (hand walkthrough)

Example input:
1 -- 2
|  / |
3 -- 4
Output: a new graph with the same connections

Walk:
- clone node 1; enqueue neighbors 2 and 3
- clone nodes 2,3,4 and wire edges as neighbors are visited
- resulting cloned graph has same 1-2-3-4 connections

Pitfalls to avoid

• Losing the one-copy-per-original correspondence. Pointer keys express it directly; value keys are also sufficient under this exercise’s unique-value promise, but do not support the repeated-value extension below.
• Creating neighbor clones without storing them first (causes duplicate nodes).
• Forgetting to handle nil input.

Debugging lens

Compare node identity as well as values. A shallow copied neighbor slice still points to originals. Preserve neighbor order rather than sorting it, and verify the source graph is unchanged.

Complexity

Time O(V + E) for the reachable component, counting adjacency entries. Auxiliary map plus recursion stack O(V); the returned graph itself occupies O(V + E). A long chain can require O(V) recursive depth.

Implementation notes (Go)

• Use map[*Node]*Node and a slice queue or recursion.
• Append neighbor clones in the same order as the original neighbors to preserve adjacency ordering.

Reconstruction checkpoint

Now relax this exercise’s unique-value promise: original A and B may share the same value. A.Neighbors=[B,B,A] and B.Neighbors=[A]. What must the clone preserve, and why would a value-keyed map cease to be sufficient?

Return to Graph General · Module quiz