Clone Graph — Deep Copy with BFS, DFS and HashMap Bookkeeping

Problem Statement#

You are given a reference to a node in a connected undirected graph. Each node holds an integer value and a list of its neighbors. Return a deep copy (clone) of the entire graph: every node and every edge must be duplicated, but the cloned graph must not share any object references with the original.

The connection list is symmetric (an undirected graph), there can be self-loops, and the graph is connected, so a single starting node lets you reach every other node.

Why This Problem Matters#

Clone Graph is one of the most asked graph problems at FAANG (Facebook, Amazon, Apple, Netflix, Google) and is a staple at Microsoft, Bloomberg, and Uber. It looks innocent but it tests four orthogonal interview skills at once: graph traversal (BFS or DFS), cycle detection through visited bookkeeping, hash map design (mapping original nodes to cloned ones), and pointer hygiene (you must not mutate the original graph). Many candidates botch this question because they treat it like a tree clone and forget that graphs have cycles, which causes infinite recursion or duplicated clones.

If you can articulate the algorithm, complexity, and edge cases for Clone Graph, you have signaled to the interviewer that you understand connected components, graph traversal mechanics, and memory management for reference types. It is the gateway problem to harder graph rewrites such as Copy List with Random Pointer, Serialize and Deserialize Graph, and Reconstruct Binary Tree from a Graph Representation.

The Core Insight#

A graph is not a tree, so a naive recursion that creates a new node and recurses into each neighbor will revisit nodes through cycles forever. The fix is to keep a cloned hash map keyed by the original node, mapping to its freshly created clone. Before you create a clone for a node, check the map; if a clone already exists, return it. This single rule turns an exponential traversal into a clean O(V plus E) walk and guarantees that every original node corresponds to exactly one cloned node.

The map serves two purposes simultaneously. It is the visited set that stops the infinite loop, and it is the lookup table that lets neighbors of any node link to the right clone instance, preserving the graph topology. Whether you traverse with DFS recursion or BFS with a queue, the map is the single source of truth for the duplicate graph.

Visual Dry Run (BFS/DFS trace)#

Consider a small graph with four nodes arranged in a square: 1 connected to 2 and 4, 2 connected to 1 and 3, 3 connected to 2 and 4, 4 connected to 1 and 3. The starting node is 1. We dry run the BFS variant.

Step one. We create a clone of node 1, store the mapping original-1 to clone-1 in our hash map, and push original-1 onto the queue.

Step two. We dequeue original-1. Its neighbors are original-2 and original-4. Neither is in the map, so we create clone-2 and clone-4, store both mappings, and push original-2 and original-4 onto the queue. We then attach clone-2 and clone-4 to clone-1's neighbor list.

Step three. We dequeue original-2. Its neighbors are original-1 (already in map, reuse clone-1) and original-3 (not in map, create clone-3, push original-3). We attach clone-1 and clone-3 to clone-2's neighbor list.

Step four. We dequeue original-4. Its neighbors are original-1 (reuse clone-1) and original-3 (already in map, reuse clone-3). We attach clone-1 and clone-3 to clone-4's neighbor list.

Step five. We dequeue original-3. Its neighbors are original-2 and original-4, both already cloned. We attach clone-2 and clone-4 to clone-3's neighbor list.

The queue is empty. Every original node was processed exactly once, every edge was traversed at most twice (once per endpoint), and the cloned graph is a perfect topological replica with brand new memory.

Solution (Optimal)#

Python — DFS with HashMap#

class Solution:
    def cloneGraph(self, node):
        if not node:
            return None
        cloned = {}
 
        def dfs(curr):
            if curr in cloned:
                return cloned[curr]
            copy = Node(curr.val)
            cloned[curr] = copy
            for nb in curr.neighbors:
                copy.neighbors.append(dfs(nb))
            return copy
 
        return dfs(node)

Python — BFS with HashMap#

from collections import deque
 
class Solution:
    def cloneGraph(self, node):
        if not node:
            return None
        cloned = {node: Node(node.val)}
        q = deque([node])
        while q:
            curr = q.popleft()
            for nb in curr.neighbors:
                if nb not in cloned:
                    cloned[nb] = Node(nb.val)
                    q.append(nb)
                cloned[curr].neighbors.append(cloned[nb])
        return cloned[node]

JavaScript — DFS#

var cloneGraph = function(node) {
    if (!node) return null;
    const cloned = new Map();
    const dfs = (curr) => {
        if (cloned.has(curr)) return cloned.get(curr);
        const copy = new Node(curr.val);
        cloned.set(curr, copy);
        for (const nb of curr.neighbors) {
            copy.neighbors.push(dfs(nb));
        }
        return copy;
    };
    return dfs(node);
};

Time complexity is O(V plus E): every node is visited once, every edge is traversed once per direction. Space complexity is O(V) for the hash map plus O(V) for the recursion stack or queue.

Common Mistakes#

Skipping the visited map is the number one bug; recursion will spiral until the stack overflows on the first cycle. Cloning a node twice happens when you create a new copy inside the neighbor loop without first checking the map, leaving the result graph with duplicate fragments that share values but are different objects. Forgetting to clone neighbors and instead pushing the original neighbor references silently leaks the original graph into the clone, which fails the deep copy test. Mutating the input graph by appending to original neighbor lists destroys the source data and is an automatic interview red flag.

Interview Tips#

State out loud that the visited map serves both as a cycle guard and as a clone lookup table; this clarifies the design. Walk the interviewer through one BFS step on a tiny example before coding. Mention you can use either BFS or DFS, but prefer BFS in interviews because the queue avoids stack overflow on deep graphs. Confirm the constraints early: is the graph connected, can the input be null, are there self-loops, and is Node.val unique. Most interviewers will mention the unique-value guarantee, which lets you key the map by integer instead of by node reference, but keying by node is safer and equally fast.

Follow-up Questions#

How would you clone a directed graph instead of an undirected one? The same algorithm works because the visited map does not depend on edge direction. How would you serialize the cloned graph so a remote service can reconstruct it? Use a level-order traversal that emits adjacency pairs. How would you parallelize the clone for very large graphs? Partition by connected component; within a component you must serialize traversal because the visited map is shared state. What if the graph contains millions of nodes and recursion blows the stack? Switch to the BFS variant, which uses an iterative queue instead of the call stack.

Key Takeaways#

• Clone Graph tests BFS, DFS, graph traversal, and hash map design at FAANG interviews
• The visited map both detects cycles and links neighbors to the correct cloned instances
• Both BFS and DFS run in O(V plus E) time and O(V) space; BFS is safer for deep graphs
• Never mutate the original graph; always allocate fresh nodes and link cloned references
• Treat null input and self-loop edges as explicit edge cases during the dry run
• Mastering this pattern unlocks Copy List with Random Pointer, Graph Serialization, and Connected Components