Clone Graph
The Prompt
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 and a list of its neighbors.
Understanding the Problem
A deep copy means brand-new node objects wired together in exactly the original shape — you cannot just copy neighbor lists, because those still point at the originals. The danger is cycles: naively cloning "this node, then its neighbors, then their neighbors..." loops forever the moment a neighbor leads back to where you started.
The cure is a hash map from original node to its clone. Cloning a node first checks the map: if a clone already exists, return it instead of making another. The map is simultaneously the visited set and the wiring directory.
The Interview Flow
Interviewer
How would you create a deep copy of a graph?
Candidate
The main challenge is to avoid getting into infinite loops if there are cycles and to make sure each node is cloned only once. I need a way to map the original nodes to their corresponding copies.
Interviewer
What data structure would you use for that mapping?
Candidate
A hash map is perfect. The keys would be the original nodes, and the values would be the newly created cloned nodes. This map will serve as a "visited" set and also give me access to the clones.
Interviewer
Describe the traversal process.
Candidate
I can use either DFS or BFS. Let's say I use DFS. I would start with the given node. In my DFS function, the first thing I do is check my hash map. If the node has already been cloned (i.e., it's in the map), I just return the clone. If not, I create a new node with the same value, put it in the map, and then recursively call the DFS function for all of its neighbors. The results of these recursive calls will be the cloned neighbor nodes, which I then add to the neighbor list of my current cloned node.
Interviewer
That sounds like a solid plan. The hash map is key to handling both the "visited" state and the mapping from old to new nodes. Please implement this recursive DFS approach.
Why does the old→new map guarantee one clone per node and correct edges?
The invariant: every original node appears in the map at most once, and its clone is created at the moment of first visit — before recursing into neighbors. So when a cycle brings the traversal back, the map already holds the clone and the recursion stops, returning the existing copy. Every edge u→v in the original becomes exactly one edge map[u]→map[v] in the copy.
Each node is cloned once and each edge is traversed once (per direction), giving O(V + E) time and O(V) space for the map plus the recursion stack. BFS works identically — the map, not the traversal order, is what makes it correct.
Recursive DFS with a Hash Map
- Create a hash map `oldToNew` to store the mapping from original nodes to their clones.
- Define a recursive `dfs` function that takes an original `node` as input.
- **Inside `dfs(node)`:**
- Handle the base case: if `node` is `null`, return `null`.
- Check if the `node` is already in `oldToNew`. If yes, it means we have already cloned this node, so just return its clone `oldToNew[node]`.
- If not, create a new node `copy` with the same value as the original `node`.
- Add the mapping to the hash map: `oldToNew[node] = copy`.
- Now, iterate through the `neighbors` of the original `node`. For each neighbor, recursively call `dfs(neighbor)`.
- Append the result of each recursive call (which is a cloned neighbor) to the `copy.neighbors` list.
- Finally, return the `copy` node.
- Start the process by calling `dfs(startNode)`.
Try it yourself
Write your solution and run it against 3 test cases.
Input shows the adjacency list; returning the original graph fails.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function cloneGraph(node) {
const oldToNew = new Map();
function dfs(original) {
if (!original) return null;
if (oldToNew.has(original)) {
return oldToNew.get(original);
}
const copy = new Node(original.val);
oldToNew.set(original, copy);
for (const neighbor of original.neighbors) {
copy.neighbors.push(dfs(neighbor));
}
return copy;
}
return dfs(node);
}Explanation
Clone the 4-node cycle 1—2—3—4—1, starting the DFS at node 1.
1The original graph: an undirected 4-cycle. Following neighbors from node 1 eventually leads back to node 1 — a naive recursive copy would never terminate.
2DFS at 1: no map entry, so create clone 1' and record 1 → 1' before touching neighbors. Recurse to neighbor 2: also new, so create 2' and wire 1' — 2'. The map now holds two entries.
3Recursion continues to 3 and 4. Node 4's other neighbor is 1 — already in the map, so it returns the existing 1' instead of cloning again, closing the cycle in the copy. Four nodes, four clones, identical shape.
Complexity Analysis
TIME
O(V + E)
SPACE
O(V)
Finished working through this one?
Mark it complete to track it on your Data Structures path.