Free lesson · DSA Mastery - Interview Prep, End to End

Clone Graph

Hard9 min readdsagraphs

Clone Graph

Clone Graph asks you to produce a deep copy of a connected undirected graph - every node and edge duplicated into a fresh structure. The technique is a DFS (or BFS) traversal that builds clones as it visits, using a HashMap from original node to its clone to (a) avoid cloning the same node twice and (b) wire up each clone's neighbors to the correct clone copies. It teaches traversal with a mapping table that doubles as the visited set, a pattern essential whenever you must reconstruct or transform a graph while preserving its structure - and it handles cycles naturally through the map. We present the DFS clone (canonical) and the BFS clone (alternative).

The insight: deep-copying a graph requires creating one clone per original node and connecting clones to mirror the originals' connections. The challenge is cycles and shared neighbors - you must not clone the same node twice, and a clone's neighbor list must point to clones, not originals. A HashMap<Node, Node> from original to clone solves both: before cloning a node, check the map; if present, return the existing clone (this is the visited check, and it breaks cycles); if absent, create the clone, record it in the map immediately, then recursively clone and attach each neighbor.

The Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

The graph is connected and given via a reference to one node. Node values are unique (commonly 1 to n).

Example 1:

Input:  adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: A 4-node cycle 1-2-3-4-1. The clone has the identical structure with new node objects.

Example 2:

Input:  adjList = [[]]
Output: [[]]

Explanation: A single node with no neighbors. Clone is a new single node.

Constraints:

Number of nodes is in [0, 100].
1 <= Node.val <= 100, values are unique.
The graph is connected, undirected, with no repeated edges or self-loops.

Approaches Overview

#	Approach	Time	Space	Verdict
1	DFS with original→clone map	O(V + E)	O(V)	Canonical
2	BFS with original→clone map	O(V + E)	O(V)	Alternative

Both traverse the graph once, creating a clone for each original node and wiring clone neighbors via a HashMap<Node, Node>. The map prevents re-cloning a node (its presence is the visited check) and resolves each neighbor to its clone. DFS clones recursively; BFS clones level by level with a queue. Both are O(V + E) - each node and edge handled once. DFS is the more concise default; the map is the essential shared ingredient that handles cycles.

Approach 1: DFS Clone - Canonical

The Idea

Keep a Map<Node, Node> from original to clone. clone(node): if node is already a key, return its stored clone (visited check + cycle break). Otherwise create copy = new Node(node.val), put node → copy into the map before recursing (so a cycle back to node finds the in-progress clone), then for each neighbor, recursively clone it and add the result to copy.neighbors. Return copy. Start with clone(start).

Logic Flowchart

graph TD
    A["clone(node)"] --> B{"node in map?"}
    B -->|Yes| C["return map[node] (already cloned - breaks cycle)"]
    B -->|No| D["copy = new Node(node.val); map[node] = copy (record BEFORE recursing)"]
    D --> E["for each neighbor nb of node"]
    E --> F["copy.neighbors.add(clone(nb))"]
    F --> E
    E --> G["return copy"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows graph cloning by DFS. If a node is already in the map its clone is returned, breaking cycles; otherwise a clone is created and recorded before recursively cloning and attaching each neighbor.

Code

public static Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> map = new HashMap<>();        // original -> clone
    return clone(node, map);
}

private static Node clone(Node node, Map<Node, Node> map) {
    if (map.containsKey(node)) return map.get(node);   // already cloned (visited + cycle break)
    Node copy = new Node(node.val);
    map.put(node, copy);                          // record BEFORE recursing into neighbors
    for (Node nb : node.neighbors)
        copy.neighbors.add(clone(nb, map));       // neighbor clones, resolved via map
    return copy;
}

// Usage: cloneGraph(reference to node 1 of a 4-cycle) -> deep copy with the same structure

This Java code clones a graph with DFS: it returns an existing clone from the map if present, otherwise creates and records a clone before recursively cloning each neighbor and attaching it.

Step-by-Step Walkthrough

A frame-by-frame trace on a small cycle 1—2—1 (two nodes, mutually connected):

graph LR
    F0["clone(1): not in map. copy1=new Node(1), map={1:copy1}"]
    F1["clone 1's neighbor 2: not in map. copy2=new Node(2), map={1:copy1, 2:copy2}"]
    F2["clone 2's neighbor 1: IN map → return copy1. copy2.neighbors=[copy1]"]
    F3["back in clone(1): copy1.neighbors=[copy2]. cycle wired correctly"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough clones a two-node cycle: node one's clone is recorded first, node two is cloned and links back to the existing clone of one via the map, wiring the cycle without infinite recursion.

Result: a deep copy with identical structure.

Complexity

Time: O(V + E) - each node cloned once, each edge traversed once. Space: O(V) for the map and recursion.

Approach 2: BFS Clone - Alternative

The Idea

Clone the start, put start → clone in the map, enqueue the start. While the queue is non-empty, dequeue an original u; for each neighbor nb, if nb isn't in the map, clone it, map it, and enqueue it; then add map[nb] to map[u]'s neighbor list. Iterative; avoids deep recursion on large graphs.

Code

public static Node cloneGraphBFS(Node node) {
    if (node == null) return null;
    Map<Node, Node> map = new HashMap<>();
    map.put(node, new Node(node.val));
    Queue<Node> q = new ArrayDeque<>();
    q.offer(node);
    while (!q.isEmpty()) {
        Node u = q.poll();
        for (Node nb : u.neighbors) {
            if (!map.containsKey(nb)) {
                map.put(nb, new Node(nb.val));    // clone unseen neighbor
                q.offer(nb);
            }
            map.get(u).neighbors.add(map.get(nb));   // wire clone-to-clone
        }
    }
    return map.get(node);
}

// Usage: cloneGraphBFS(reference to node 1) -> deep copy

This Java code clones a graph with BFS: it clones the start, then for each dequeued node clones any unseen neighbor and wires the clone's neighbor list to the corresponding clones via the map.

Complexity

Time: O(V + E). Space: O(V) for the map and queue.

Complexity Comparison

Approach	Time	Space	Key Idea
DFS clone	O(V + E)	O(V)	Map original→clone; recurse, wire neighbors
BFS clone	O(V + E)	O(V)	Map original→clone; queue, wire neighbors

Both deep-copy the graph in O(V + E) using a HashMap<Node, Node> that simultaneously serves as the visited set (a node already mapped is already cloned) and the resolver (each neighbor maps to its clone). The map breaks cycles automatically - revisiting a node returns its existing clone instead of recursing forever. DFS is concise; BFS avoids deep recursion. The mapping table is the central technique.

Variations & Follow-ups

Why does the original→clone map serve as both the visited set and the neighbor resolver?

The map does double duty, which is what makes the algorithm clean. First, as a visited set: a node is in the map exactly when it has been cloned, so checking map.containsKey(node) before cloning prevents creating a second clone of the same node - and, crucially, prevents infinite recursion on cycles (revisiting a node returns its existing clone rather than recursing). Second, as a resolver: when wiring up a clone's neighbor list, each original neighbor must be replaced by its clone, and map.get(neighbor) provides exactly that. A plain boolean visited array couldn't do the second job - it would tell you a node was visited but not give you the clone object to link to. The map's key insight is that "have I cloned this?" and "what is this node's clone?" are the same question, answered by one lookup. This unification of visited-tracking and clone-resolution into a single map is the elegant core of graph cloning and of graph-transformation problems generally: when you're building a parallel structure, a map from old to new handles both deduplication and reference-fixing at once.

Why must you record a node's clone in the map before recursing into its neighbors?

The ordering is critical for handling cycles correctly. Consider a cycle 1 → 2 → 1. When cloning node 1, if you recursed into neighbor 2 before putting 1 → clone1 in the map, then while cloning 2 you'd recurse into 2's neighbor 1, find 1 not yet in the map, and clone it again - creating a second clone of 1 and recursing infinitely. By inserting 1 → clone1 into the map immediately upon creating clone1, before exploring 1's neighbors, the recursive descent into 2 → 1 finds 1 already in the map and returns the existing clone1, terminating the cycle and wiring 2's clone back to the correct, single clone of 1. This "register the clone before recursing" rule is the cycle-safety guarantee - it ensures every node is cloned exactly once even when paths loop back. It mirrors DFS's "mark visited on entry, not after processing neighbors" discipline: you must record your presence before exploring, so that a cycle returning to you sees the record. Inserting the clone after recursing reopens the infinite-clone bug, the canonical mistake in this problem.

Why is a deep copy required, and what would a shallow copy get wrong?

A deep copy means every node and the entire neighbor structure is duplicated into fresh objects, completely independent of the original - modifying the clone never affects the original and vice versa. A shallow copy would create new node objects but have their neighbor lists still point to the original nodes (or share the original lists), so the "clone" would be entangled with the original graph. The problem demands a deep copy: each clone's neighbors must be the clones of the original's neighbors, forming a self-contained duplicate graph. This is exactly why the map resolves neighbors to clones - copy.neighbors.add(clone(nb)) attaches the neighbor's clone, not the original neighbor. If you mistakenly wrote copy.neighbors.add(nb), you'd link the clone to original nodes, producing a corrupt half-cloned structure. The deep-copy requirement is what forces the careful clone-resolution via the map; a shallow copy would be trivial (just copy references) but wrong. Recognizing "deep copy" as "duplicate everything, with internal references pointing within the duplicate" is the framing that makes the map-based resolution necessary.

Where else does the "traverse with a mapping table" pattern apply?

The map-from-original-to-new pattern is the signature of graph and structure reconstruction problems. It appears in: Copy List with Random Pointer (deep-copy a linked list where nodes have an extra random pointer - a map from original to copy resolves both next and random pointers), serialize/deserialize structures (a map reconnects references during rebuild), constructing a graph from a description while deduplicating nodes by id, and any transformation that must preserve internal structure while producing fresh objects. The unifying idea: when you traverse a structure to build a parallel one, maintain a map from each original element to its counterpart, so that (a) you build each counterpart once and (b) you can resolve any reference to its counterpart. This handles cycles, shared substructure, and back-references automatically. Clone Graph is the canonical teaching instance because undirected graphs have cycles and shared neighbors, exercising both jobs of the map. Once you internalize "reconstruction needs an old→new map that doubles as visited," a whole class of deep-copy and rebuild problems becomes routine.

What about edge cases?

Null input: Return null (empty graph).
Single node, no neighbors (Example 2): Clone is one new node with an empty neighbor list.
Cycle (Example 1, a 4-cycle): The map breaks the cycle; each node cloned once, neighbors wired to clones.
Self-loop (excluded here, but generally): The map returns the node's own clone, wiring the self-loop correctly.
Densely connected graph: Each edge handled once; the map ensures clones are shared, not duplicated.

Common Interview Pitfalls

Recording the clone after recursing. Causes infinite recursion / duplicate clones on cycles; map the clone before exploring neighbors.
Linking clones to original neighbors. Use map.get(neighbor) to attach the neighbor's clone, not the original.
Using a boolean visited array. It can't resolve a node to its clone; the map is required for the wiring.
Forgetting the null-input check. A null reference should return null, not crash.

Why This Topic Matters

Clone Graph teaches traversal with a mapping table: a HashMap<Node, Node> from original to clone serves simultaneously as the visited set (already-mapped = already-cloned, breaking cycles) and the neighbor resolver (each clone's neighbors point to clones). The "record the clone before recursing" rule ensures cycle safety. This old→new map pattern is the backbone of deep-copy and graph-reconstruction problems, from Copy List with Random Pointer to serialize/deserialize.

The next topic, Is Graph Bipartite?, revisits the bipartite check from the introduction sub-group, now as an explicit problem on an adjacency-list input. A graph is bipartite if its vertices can be 2-colored so that no edge joins same-colored vertices; the technique is the DFS/BFS two-coloring established earlier, applied here with the standard disconnected-graph handling (try every uncomponent). It reinforces the alternating-color traversal and the odd-cycle obstruction, consolidating the introduction sub-group's coloring concept into a directly-posed problem you will recognize instantly.

Back to DSA Mastery - Interview Prep, End to End