Abstract / Summary

Given a reference to a node in a connected undirected graph with next pointers return a deep copy of the entire graph.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (3+ million submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph Theory
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class that clones an undirected graph represented by nodes of type Node. The algorithm proceeds in two distinct phases. First, it traverses the original graph to build an adjacency map (self.edges) that records each node’s value and the values of its neighboring nodes. Second, it creates a new set of Node instances and wires their neighbor relationships according to the previously built map. The result is a deep copy of the input graph, with the same topology but independent node objects.

Phase 1 - Building the adjacency map

The method createEdges performs a depth-first traversal starting from a given node. It checks whether the node is None or has already been visited (its value appears in self.edges). If either condition holds, the recursion stops, preventing infinite loops on cyclic graphs and avoiding duplicate work.

def createEdges(self, node):
    if not node or node.val in self.edges:
        return

    self.edges[node.val] = []
    for i in node.neighbors:
        self.edges[node.val].append(i.val)
        self.createEdges(i)

Key actions in this phase:

• Initialization of an empty list for the current node’s adjacency entry.
• Iteration over each neighbor, appending the neighbor’s value to the list.
• Recursive call on each neighbor to continue the traversal.

Because the method records a node’s value before recursing, any subsequent encounter of the same node is short-circuited by the node.val in self.edges guard. This handles graphs that contain cycles, self-loops, or multiple paths to the same node, ensuring each vertex is processed exactly once.

Phase 2 - Instantiating clone nodes

After the adjacency map is populated, cloneGraph creates a dictionary clone that maps each original node value to a newly allocated Node object with the same value but an initially empty neighbor list.

clone = {}
for e in self.edges:
    clone[e] = Node(e)

This step isolates node creation from neighbor wiring, allowing all node objects to exist before any references are established. The approach eliminates the need for on-the-fly creation during neighbor linking, which could otherwise require checking for the existence of a target node repeatedly.

Phase 3 - Reconstructing neighbor relationships

With all clone nodes in place, the algorithm iterates over the adjacency map a second time. For each entry, it looks up the corresponding clone node and appends the clones of its neighbors, using the pre-built clone dictionary for constant-time access.

for e in self.edges:
    for other in self.edges[e]:
        clone[e].neighbors.append(clone[other])

Because the neighbor lists are built from values rather than object references, the code avoids accidental sharing of neighbor lists between the original and cloned graphs. The final statement returns the clone that corresponds to the original entry point.

return clone[node.val]

Edge-case handling

The implementation explicitly checks for a None input at the start of cloneGraph. When the input graph is empty, the method returns None immediately, satisfying the contract for an empty graph.

The recursion guard node.val in self.edges ensures that graphs containing cycles, including self-referential nodes (a node that lists itself as a neighbor), do not cause infinite recursion. By marking a node as visited before exploring its neighbors, the algorithm safely processes any graph topology, regardless of connectivity or the presence of multiple components reachable from the start node.

Performance-related choices

The two-pass strategy-first building an adjacency map, then constructing nodes and linking neighbors-offers several performance benefits. Recording adjacency information as plain integer lists (self.edges[node.val] = []) provides fast appends and compact storage, avoiding the overhead of storing full node objects during traversal. The subsequent node creation loop runs in linear time relative to the number of distinct node values, and the neighbor-linking loop also runs linearly with respect to the total number of edges, because each edge is processed exactly once.

Using dictionaries (self.edges and clone) for lookups yields constant-time access when checking visitation status, creating a node, or retrieving a neighbor’s clone. This eliminates the need for linear scans to locate nodes, which would degrade performance on large graphs.

By separating node allocation from neighbor wiring, the code avoids repeated conditional checks for the existence of a neighbor’s clone during edge reconstruction. All clones are guaranteed to exist before any neighbor list is populated, allowing the inner loop to focus solely on appending references, which is a minimal-overhead operation.

Overall, the design leverages depth-first traversal for discovery, dictionary-based memoization for fast existence checks, and a clear two-phase construction pipeline to achieve an efficient deep copy of an arbitrary undirected graph.

Imagine you have a drawing of a constellation made of stars connected by lines. This code is like building a perfect double of that constellation.

First, the code goes through the drawing starting from one star and follows every single line to find all the other stars it can reach. As it visits each star, it writes down the name of that star and the names of all the other stars it is connected to in a secret notebook. It keeps doing this until every star has been found and its friends have been written down.

Once the notebook is full of these lists, the code starts making a second set of blank stars that match the ones from the first drawing. It looks at the notebook again to see who should be connected to whom. It carefully draws new lines between these new stars to make sure they look exactly like the connections in the first drawing. After all the lines are drawn, a identical version of the original constellation is ready to play with.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#		JS			Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	DimitrisJim					C
	everthis						JS
	fartem							Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	gouthampradhan			Java
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02					C
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality