Clone Graph

Learning goal: Recognize why cloning a graph requires both traversal and identity tracking.

Core idea A graph is not a tree: one node can be reached through multiple paths, and cycles can lead back to nodes already being processed. We must create a new object for each original node while preserving every neighbor relationship. The output must share no node objects with the input graph.

Algorithm plan

• Start from the given node; return null if it does not exist.
• Traverse reachable nodes with DFS or BFS.
• Store the relationship original node → cloned node in a hash map.
• For each edge, connect the current clone to the clone of its neighbor.

Micro-example For the edge 1 — 2, create clones 1' and 2', then add 2' to 1''s neighbors and 1' to 2''s neighbors. If the traversal encounters node 1 again, reuse 1'.

Pitfalls

• Returning the original node instead of a structurally identical copy.
• Treating the graph like a tree and ignoring repeated visits.
• Forgetting that an empty input should produce null.

Recap

• Traverse every reachable node and edge.
• Preserve structure, but allocate independent node objects.
• Identity tracking is essential for cycles and shared neighbors.

Learning goal: Understand how one hash map acts as both memoization and cycle protection.

Core idea Maintain clones, where clones[original] is the unique copy of that original node. The moment a node is first discovered, create and store its clone before exploring neighbors. Later encounters find the existing clone instead of allocating another object or recursing forever.

Data structure model

Micro-example Starting at 1, create 1' and store it immediately. When node 3 later sees neighbor 1, clones already contains 1 → 1', so the edge points back to the existing clone.

Pitfalls

• Checking the map only after recursive traversal is too late.
• Mapping by node value can be unsafe if values are not guaranteed unique.
• Creating a clone but postponing insertion allows cycles to re-enter the same work.

Recap

• Insert each clone into the map at discovery time.
• Reuse mapped clones whenever an edge points to a seen node.
• This guarantees one clone per original node.

Learning goal: Translate the map idea into a correct traversal algorithm.

Core idea DFS and BFS differ only in traversal order; both use the same clone map. For each original node, its clone is guaranteed to exist before we process its adjacency list. Every neighbor is either retrieved from the map or created and added to the frontier.

Algorithm plan

1. If start is null, return null.
2. Create startClone, and set clones[start] = startClone.
3. Put start into a queue for BFS, or call dfs(start).
4. For each original neighbor:
   • Create and map its clone if unseen.
   • Append the mapped clone to the current clone's neighbors.
   • Enqueue or recurse into the neighbor only when it was newly created.
5. Return clones[start].

clones = {start: Node(start.val)}
queue = deque([start])
while queue:
    node = queue.popleft()
    for neighbor in node.neighbors:
        if neighbor not in clones:
            clones[neighbor] = Node(neighbor.val)
            queue.append(neighbor)
        clones[node].neighbors.append(clones[neighbor])
return clones[start]

Micro-example When BFS processes node 2, neighbor 1 is already mapped, while neighbor 3 is new. Reuse 1', create 3', and connect both from 2'.

Pitfalls

• Enqueuing a node repeatedly can cause unnecessary work.
• Adding an edge to the original neighbor corrupts independence.
• For undirected edges, each adjacency list must be copied as given.

Recap

• Discovery creates and maps; processing wires neighbors.
• BFS and DFS have the same correctness invariant.
• Return the clone associated with the original start node.

Learning goal: Trace how BFS creates each clone exactly once and reconstructs all edges.

Core idea Use the example graph with adjacency lists 1: [2, 4], 2: [1, 3], 3: [2, 4], and 4: [1, 3]. It contains a cycle, so the walkthrough makes the map's protection especially visible. We mark a node as discovered when its clone is created, not when it is removed from the queue.

Algorithm plan

• Initialize clones = {1: 1'} and queue [1].
• Process node 1; create clones 2' and 4', and wire 1' to both.
• Process node 2; reuse 1', create 3', and wire 2' to both.
• Process nodes 4 and 3; every neighbor is already mapped, so only edges are added.
• Finish with four clones and the same adjacency relationships.

Micro-example The edge 4 — 1 does not create another copy of 1. The map returns 1', preserving the cycle while guaranteeing termination.

Pitfalls

• A node can be in the map while still waiting in the queue.
• “Seen” means clone created, not necessarily traversal completed.
• The final graph should contain four clone objects, not copies per incoming edge.

Recap

• Four original nodes produce four and only four clones.
• Existing map entries are reused for back-edges.
• Every original adjacency entry becomes a clone adjacency entry.

Learning goal: Diagnose the most common correctness bug and handle boundary cases confidently.

Core idea The dangerous mistake is creating a clone only after exploring neighbors. In a cycle, recursion or traversal can encounter the same original node before its first clone has been registered. That creates duplicate clones—or causes infinite recursion. Register the clone immediately, then process its neighbors.

Algorithm plan

• Handle start == null before accessing its value.
• Use node identity as the map key; the map must distinguish object references.
• Check clones before creating or enqueuing a neighbor.
• Add every neighbor reference to the current clone, including references to already processed nodes.

Micro-example For 1 — 2 — 1, DFS creates 1', then 2'. At 2's neighbor 1, the map returns 1'; it must not allocate 1''.

Pitfalls

• Marking a node only after recursive calls is too late.
• Copying values without copying adjacency lists produces isolated nodes.
• Forgetting the null input case causes an invalid dereference.

Recap

• Map first, recurse or enqueue second.
• Reuse clones for every repeated encounter.
• Null, isolated, cyclic, and fully connected graphs all follow the same rule.

Learning goal: Justify the O(V + E) runtime and O(V) auxiliary space bound.

Core idea Each reachable node is discovered and processed once because the map prevents duplicate frontier entries. While processing a node, we inspect its adjacency list; across the whole graph, those inspections account for the graph's edges. For an undirected adjacency representation, each logical edge may appear twice, but that constant factor does not change the asymptotic bound.

Algorithm plan

• Charge one map insertion to each of the V nodes.
• Charge one neighbor inspection to each adjacency entry, totaling O(E) up to representation constants.
• Store at most one clone and one frontier entry per original node.
• Return the mapped clone for the starting node.

Micro-example The four-node cycle has V = 4 and four logical edges. BFS creates four clones and inspects eight adjacency entries: linear work in the input size.

Pitfalls

• Counting only nodes and forgetting adjacency inspection underestimates time.
• Calling recursion stack space O(1) is incorrect: DFS can hold O(V) frames.
• The output graph itself contains O(V + E) data, separate from auxiliary map and frontier space.

Recap

• Time: O(V + E).
• Auxiliary space: O(V) for the map and traversal frontier.
• The invariant is one unique clone per reachable original.