Clone Graph — DFS With a Node-to-Copy Hash Map

Clone Graph is what happens when someone tries to make “implement deep copy” sound like an algorithm question. It is, but only barely: the entire problem reduces to one decision — how do you keep track of what you have already cloned? A hash map keyed on the original node is the only sane answer, and once that is in place the rest is a textbook traversal.

The Problem

You are given a reference to a node in a connected undirected graph. Each node has a value and a list of neighbors. Return a deep copy of the graph: every node must be a new object, the edge structure must match, and no part of the new graph may share references with the original.

Intuition

Maintain a dictionary clones from original node to its copy. When you visit a node, return the existing copy if present; otherwise create a new node, store it immediately (before recursing), then recurse into neighbors and fill in the copy’s neighbor list. Storing the new node before recursing is the load-bearing step. It breaks cycles by ensuring that when a recursive call comes back around to the same original node, the map already has an answer.

Explanation with Example

A 4-node cycle: 1 - 2 - 3 - 4 - 1 with the obvious cross edges between 2-4.

• Start DFS at 1. Create copy 1’. Store 1 -> 1'. Recurse into neighbor 2.
• Create copy 2’. Store 2 -> 2'. Recurse into 1 (already mapped, return 1’), into 3, into 4.
• 3 creates 3’, stores, recurses into 2 (mapped) and 4.
• 4 creates 4’, stores, recurses into 1 (mapped), 3 (mapped).

Every edge gets walked once per side, but every node is created exactly once. The map keeps the work bounded.

original graph:        clones map grows step by step:
 1 --- 2             step 1: {1: 1'}
 |     |             step 2: {1: 1', 2: 2'}
 4 --- 3             step 3: {1: 1', 2: 2', 3: 3'}
                     step 4: {1: 1', 2: 2', 3: 3', 4: 4'}

DFS at 2 -> neighbor 1 already in map -> return 1' (no infinite loop)

cloned graph (same shape, new nodes):
 1' --- 2'
 |      |
 4' --- 3'

Code

def cloneGraph(node):
    if not node:
        return None
    clones = {}

    def dfs(orig):
        if orig in clones:
            return clones[orig]
        copy = Node(orig.val, [])
        clones[orig] = copy
        for nbr in orig.neighbors:
            copy.neighbors.append(dfs(nbr))
        return copy

    return dfs(node)

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> clones = new HashMap<>();
    return dfs(node, clones);
}

private Node dfs(Node orig, Map<Node, Node> clones) {
    if (clones.containsKey(orig)) return clones.get(orig);
    Node copy = new Node(orig.val, new ArrayList<>());
    clones.put(orig, copy);
    for (Node nbr : orig.neighbors) {
        copy.neighbors.add(dfs(nbr, clones));
    }
    return copy;
}

Node* dfs(Node* orig, unordered_map<Node*, Node*>& clones) {
    auto it = clones.find(orig);
    if (it != clones.end()) return it->second;
    Node* copy = new Node(orig->val);
    clones[orig] = copy;
    for (Node* nbr : orig->neighbors) {
        copy->neighbors.push_back(dfs(nbr, clones));
    }
    return copy;
}

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> clones;
    return dfs(node, clones);
}

Edge Cases

• Empty input (null node) — return null.
• A single isolated node — clone it with an empty neighbor list.
• Self-loops — handled. When you recurse from a node back to itself, the map already has the copy.
• Disconnected components — the problem assumes connectivity. If real interview clarification reveals otherwise, you would need to iterate over all entry points.
• Multigraphs — neighbors may repeat. The hash map keeps node identity correct; duplicate edges become duplicate references, which matches the input.

Complexity Analysis

Let n be the number of nodes and m the number of edges. Time is O(n + m) — every node and every edge is processed a constant number of times. Space is O(n) for the clone map plus O(n) for the recursion stack in DFS or the queue in BFS.

If the recursion stack matters (deep graphs, sandboxed runtimes), pick BFS. Otherwise pick whichever you can write fastest. For the underlying complexity framing, see Big-O Notation Explained.

How to Explain It in an Interview

Lead with the cycle hazard. “Without memoization I will either loop forever or create duplicates, so I need a map from original node to its copy.” Then walk through the two-line ordering: create the copy, store it in the map, then recurse. State explicitly that the early store is what breaks cycles.

If the interviewer asks “what changes if the graph is directed?” — nothing, the same DFS works. If they ask “what changes if node values are unique?” — you could key the map on val, but keying on identity (the node object itself) is safer because uniqueness is a property of the input, not the algorithm.

Related Problems

• Copy List with Random Pointer (same map-from-original idea)
• Clone N-ary Tree
• Number of Islands (BFS/DFS on a grid; the BFS skeleton transfers directly)
• Is Graph Bipartite (graph traversal with state)

For more on building the BFS reflex that shows up in nearly all of these, see BFS and DFS.

Wrap up

Clone Graph is the canonical example of “use a hash map as your traversal memory.” Once you internalize the create-then-store-then-recurse order, you can solve every deep-copy variant in the catalog with a one-paragraph mental model.