Clone Graph — Solution

Problem

Given a reference to a node in a connected undirected graph, produce a complete deep copy of the entire graph. Every node has an integer value and a list of its neighbors. The clone must be structurally identical to the original but fully independent — no cloned node should point back to any original node.

Consider a 4-node cycle where each node's value equals its 1-based index: node 1 connects to nodes 2 and 4, node 2 connects to nodes 1 and 3, node 3 connects to nodes 2 and 4, and node 4 connects to nodes 3 and 1.

• Input: adjList = [[2,4],[1,3],[2,4],[3,1]]
• Output: [[2,4],[1,3],[2,4],[3,1]] (a structurally identical but independent graph)
• Explanation: the adjacency list of the clone matches the original, but every node object is a distinct new instance

Intuition

The challenge is that graphs can have cycles — following every edge naively to clone neighbors would loop forever. The key insight is to use a hash map that tracks which original nodes have already been cloned, so when you encounter a node you've seen before you return its existing clone rather than creating a duplicate. Once this guard is in place, a single DFS from the starting node visits and clones the entire connected component.

Solution — DFS with Visited Map

Register each clone in the hash map immediately upon creation, before recursing into its neighbors. This way, any back-edge to an already-seen node retrieves the existing clone instead of spawning a new one, naturally breaking cycles.

1. Return None if the input node is None (empty graph edge case)
2. If the current node already exists in cloned, return cloned[node] — handles cycles and revisits
3. Create a new node clone = Node(node.val) with an empty neighbor list
4. Immediately register: cloned[node] = clone (must happen before recursing, not after)
5. For each neighbor of the original node, recursively clone it and append to clone.neighbors
6. Return clone

1class Solution:
2    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
3        cloned = {}  # maps original node → its clone
4
5        def dfs(original):
6            if original in cloned:
7                return cloned[original]  # reuse existing clone to avoid infinite cycles
8
9            clone = Node(original.val)
10            cloned[original] = clone  # register before recursing so back-edges find this clone
11
12            for neighbor in original.neighbors:
13                clone.neighbors.append(dfs(neighbor))
14
15            return clone
16
17        return dfs(node) if node else None

Time: O(V + E) — each node is visited exactly once and each edge is traversed once to build neighbor lists

Space: O(V) — the hash map stores one entry per node; the recursion stack depth is O(V) in the worst case (a path-shaped graph)

Complexity Summary

Common Mistakes

• Registering the clone after recursing into neighbors instead of before — the registration must happen before the recursive calls; if a back-edge to the current node fires first, it finds nothing in the map and spawns a duplicate, corrupting the graph structure
• Checking the map but creating a new node anyway — doing clone = Node(node.val) unconditionally and then checking the map discards the early-return benefit and creates extra nodes that never get connected
• Not handling a None/null input node — LeetCode passes null to represent an empty graph; forgetting this causes a null pointer crash before any DFS logic runs
• Using the clone as the hash map key — lookups check whether an original node has been processed; keying on the clone means every node looks "new", cycles never break, and the stack overflows
• Shallow-copying the neighbor list — writing clone.neighbors = node.neighbors copies a reference to the original list; any change to either graph's neighbor list then affects both, breaking the independence guarantee

Related Problems

• number-of-islands — DFS/BFS traversal to identify connected components, same visited-set technique
• find-if-path-exists-in-graph — basic graph reachability using the same pattern of marking nodes seen before recursing
• number-of-provinces — finding connected components in an undirected graph with DFS or union-find
• all-paths-from-source-to-target — DAG traversal building output as you go, mirroring the "construct while visiting" DFS structure here
• course-schedule — cycle detection in a directed graph; the same visited-map approach prevents revisiting nodes during DFS