LeetCode Problem 133

Difficulty: 🟡 Medium
Topics: Hash Table, Depth-First Search, Breadth-First Search, Graph Theory

Solution

Clone Graph

Problem Understanding

This problem asks us to create a deep copy of an undirected connected graph. We are given a reference to one node in the graph, and we must return a completely independent copy of the entire graph structure.

Each graph node contains two pieces of information:

• val, an integer uniquely identifying the node
• neighbors, a list of adjacent nodes

A deep copy means the cloned graph must contain entirely new node objects. The cloned nodes should preserve the exact same connectivity structure as the original graph, but none of the original node objects may be reused.

The graph is represented conceptually as an adjacency list. For example:

[[2,4],[1,3],[2,4],[1,3]]

means:

• Node 1 connects to nodes 2 and 4
• Node 2 connects to nodes 1 and 3
• Node 3 connects to nodes 2 and 4
• Node 4 connects to nodes 1 and 3

The important part is that graphs may contain cycles. Unlike trees, where every node has a single parent, graphs can revisit previously seen nodes through different paths. This is the central challenge of the problem.

The constraints are relatively small:

• At most 100 nodes
• Node values are unique
• No self loops
• No duplicate edges
• The graph is connected

Even though the graph is small, a naive recursive solution without cycle handling would fail because cyclic graphs can cause infinite recursion.

Several important edge cases must be handled carefully:

• The input node may be None, representing an empty graph
• The graph may contain a single node with no neighbors
• The graph may contain cycles
• Multiple nodes may reference the same neighbor, requiring consistent reuse of cloned nodes

The key challenge is ensuring that every original node maps to exactly one cloned node.

Approaches

Brute Force Approach

A naive approach would recursively clone every node and its neighbors without tracking which nodes have already been copied.

The algorithm would look something like this:

1. Create a clone of the current node
2. Recursively clone each neighbor
3. Attach the cloned neighbors to the cloned node

At first glance, this seems reasonable because recursion naturally follows graph edges.

However, this approach breaks immediately when cycles exist.

Consider this graph:

1 -- 2

Since the graph is undirected:

• Node 1 references node 2
• Node 2 references node 1

If we recursively clone neighbors without remembering previously cloned nodes:

• Cloning node 1 clones node 2
• Cloning node 2 clones node 1 again
• Cloning node 1 clones node 2 again
• This continues forever

Even if infinite recursion were somehow prevented, the algorithm would incorrectly create multiple copies of the same logical node.

The core problem is that graphs are not hierarchical structures. Nodes may be revisited through different traversal paths.

Optimal Approach

The key insight is that each original node must correspond to exactly one cloned node.

This naturally suggests using a hash map:

original node -> cloned node

Whenever we encounter a node:

• If it has already been cloned, reuse the existing clone

• Otherwise:

• Create a new clone

• Store it in the hash map immediately

• Recursively clone its neighbors

This solves both major problems:

• Prevents infinite recursion in cyclic graphs
• Ensures structural consistency by reusing cloned nodes

We can implement this using either DFS or BFS traversal. DFS with recursion is the most concise and natural solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Infinite in cyclic graphs	Unbounded	Repeatedly revisits nodes and causes infinite recursion
Optimal	O(V + E)	O(V)	Uses a hash map to avoid duplicate cloning

Where:

• V = number of vertices (nodes)
• E = number of edges

Algorithm Walkthrough

DFS + Hash Map Algorithm

1. First, handle the empty graph case.

If the input node is None, return None immediately because there is nothing to clone. 2. Create a hash map to store mappings from original nodes to cloned nodes.

This map is the core of the algorithm. It guarantees that each original node is cloned exactly once.

Example:

visited[original_node] = cloned_node

3. Define a recursive DFS function.

The DFS function receives an original node and returns its cloned version. 4. Inside the DFS function, first check whether the node has already been cloned.

If the node exists in the hash map, return the previously created clone immediately.

This prevents:

• Infinite recursion
• Duplicate node creation

5. If the node has not been cloned yet, create a new clone node.

Initially, the cloned node has:

• The same value
• An empty neighbor list

6. Store the clone in the hash map immediately.

This step is critical.

We store the clone before processing neighbors so cyclic references can safely reuse it during recursion. 7. Traverse all neighbors of the current node.

For each neighbor:

• Recursively clone it using DFS
• Append the cloned neighbor to the current cloned node's neighbor list

8. After all neighbors are processed, return the cloned node.
9. Start DFS from the input node and return the resulting clone.

Why it works

The algorithm maintains the invariant that every original node is mapped to exactly one cloned node in the hash map.

Whenever a node is revisited through another traversal path, the existing clone is reused instead of creating a new one. Since every edge is reconstructed using these consistent cloned references, the final graph preserves the exact structure of the original graph.

Because the algorithm visits each node and edge only once, it correctly clones cyclic graphs without infinite recursion.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None

        cloned_nodes = {}

        def dfs(current: 'Node') -> 'Node':
            if current in cloned_nodes:
                return cloned_nodes[current]

            clone = Node(current.val)
            cloned_nodes[current] = clone

            for neighbor in current.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone

        return dfs(node)

The implementation begins by handling the empty graph case. If the input node is None, the function immediately returns None.

The cloned_nodes dictionary acts as the mapping between original nodes and their cloned counterparts. This is the mechanism that prevents duplicate cloning and infinite recursion.

The recursive dfs function performs the actual graph traversal and cloning.

The first operation inside dfs checks whether the current node has already been cloned. If so, the stored clone is returned immediately.

If the node has not been cloned yet, a new Node instance is created with the same value. The clone is stored in the dictionary before processing neighbors. This ordering is essential because cyclic graphs may revisit the node during recursion.

The algorithm then iterates through every neighbor of the current node. Each neighbor is recursively cloned, and the resulting cloned neighbor is appended to the current clone's neighbor list.

Finally, the cloned version of the input node is returned.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    clonedNodes := make(map[*Node]*Node)

    var dfs func(*Node) *Node

    dfs = func(current *Node) *Node {
        if clone, exists := clonedNodes[current]; exists {
            return clone
        }

        clone := &Node{
            Val: current.Val,
        }

        clonedNodes[current] = clone

        for _, neighbor := range current.Neighbors {
            clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
        }

        return clone
    }

    return dfs(node)
}

The Go implementation follows the exact same logic as the Python version.

The primary difference is that Go uses explicit pointer types:

map[*Node]*Node

This map stores pointers to original nodes and pointers to cloned nodes.

Go also requires explicit slice appending for neighbor lists:

clone.Neighbors = append(clone.Neighbors, dfs(neighbor))

The empty graph case is handled using nil instead of Python's None.

Since node values are small integers and no arithmetic is performed, integer overflow is not a concern in this problem.

Worked Examples

Example 1

Input:
[[2,4],[1,3],[2,4],[1,3]]

Graph structure:

1 -- 2
|    |
4 -- 3

Step-by-Step Trace

Step	Current Node	Action	Hash Map State
1	1	Create clone of 1	{1: clone1}
2	2	Clone neighbor 2	{1: clone1, 2: clone2}
3	1	Already cloned, reuse	unchanged
4	3	Clone neighbor 3	{1: clone1, 2: clone2, 3: clone3}
5	2	Already cloned, reuse	unchanged
6	4	Clone neighbor 4	{1: clone1, 2: clone2, 3: clone3, 4: clone4}
7	1	Already cloned, reuse	unchanged
8	3	Already cloned, reuse	unchanged

Final Cloned Structure

clone1 -> [clone2, clone4]
clone2 -> [clone1, clone3]
clone3 -> [clone2, clone4]
clone4 -> [clone1, clone3]

The cloned graph preserves the original structure exactly.

Example 2

Input:
[[]]

Graph structure:

1

Step-by-Step Trace

Step	Current Node	Action	Hash Map State
1	1	Create clone of node 1	{1: clone1}
2	none	No neighbors to process	unchanged

Final Result

clone1.neighbors = []

The single isolated node is cloned correctly.

Example 3

Input:
[]

This represents an empty graph.

Step-by-Step Trace

Step	Current Node	Action
1	None	Return None immediately

Final Result

None

The algorithm correctly handles the empty input.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V + E)	Each node and edge is visited exactly once
Space	O(V)	Hash map and recursion stack store up to V nodes

The time complexity is linear in the size of the graph because every node is cloned once and every edge is traversed once.

The space complexity comes primarily from the hash map storing cloned nodes. The recursion stack may also grow to O(V) in the worst case for a deeply connected graph.

Test Cases

# Definition for testing
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def cloneGraph(self, node):
        if not node:
            return None

        cloned_nodes = {}

        def dfs(current):
            if current in cloned_nodes:
                return cloned_nodes[current]

            clone = Node(current.val)
            cloned_nodes[current] = clone

            for neighbor in current.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone

        return dfs(node)

def compare_graphs(node1, node2, visited=None):
    if visited is None:
        visited = set()

    if node1 in visited:
        return True

    visited.add(node1)

    assert node1 is not node2
    assert node1.val == node2.val
    assert len(node1.neighbors) == len(node2.neighbors)

    for n1, n2 in zip(node1.neighbors, node2.neighbors):
        compare_graphs(n1, n2, visited)

    return True

solution = Solution()

# Test 1: Empty graph
assert solution.cloneGraph(None) is None  # handles empty input

# Test 2: Single isolated node
node1 = Node(1)
clone1 = solution.cloneGraph(node1)

assert clone1 is not node1  # deep copy
assert clone1.val == 1
assert clone1.neighbors == []  # no neighbors

# Test 3: Two connected nodes
node1 = Node(1)
node2 = Node(2)

node1.neighbors = [node2]
node2.neighbors = [node1]

clone = solution.cloneGraph(node1)

assert clone.val == 1  # root preserved
assert clone.neighbors[0].val == 2  # neighbor cloned
assert clone.neighbors[0] is not node2  # deep copy
assert clone.neighbors[0].neighbors[0] is clone  # cyclic link preserved

# Test 4: Four-node cycle graph
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

n1.neighbors = [n2, n4]
n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]
n4.neighbors = [n1, n3]

clone = solution.cloneGraph(n1)

assert compare_graphs(n1, clone)  # full graph structure preserved

# Test 5: Triangle graph
a = Node(1)
b = Node(2)
c = Node(3)

a.neighbors = [b, c]
b.neighbors = [a, c]
c.neighbors = [a, b]

clone = solution.cloneGraph(a)

assert clone.val == 1  # correct root
assert len(clone.neighbors) == 2  # preserves adjacency

# Test 6: Verify deep copy independence
node1 = Node(1)
node2 = Node(2)

node1.neighbors = [node2]
node2.neighbors = [node1]

clone = solution.cloneGraph(node1)

clone.val = 100

assert node1.val == 1  # original graph unaffected

Test Case Summary

Test	Why
Empty graph	Verifies handling of None input
Single node	Verifies isolated node cloning
Two connected nodes	Verifies cyclic references
Four-node cycle	Verifies general graph cloning
Triangle graph	Verifies multiple neighbor handling
Deep copy independence	Verifies cloned graph is fully independent

Edge Cases

Empty Graph

The input may be None, representing a graph with no nodes.

This case is easy to overlook because many graph algorithms assume at least one node exists. Attempting to access neighbors of a None object would immediately cause an error.

The implementation handles this safely with:

if not node:
    return None

This ensures the algorithm exits before any traversal logic begins.

Cyclic Graphs

Graphs commonly contain cycles, especially undirected graphs.

Without tracking visited nodes, recursion would repeatedly revisit the same nodes forever, eventually causing stack overflow or infinite recursion.

The hash map prevents this problem by storing cloned nodes immediately after creation. Whenever a node is revisited, the existing clone is reused instead of recursively cloning again.

This is the most important correctness condition in the problem.

Multiple References to the Same Node

A graph may contain several paths leading to the same node.

For example:

1 -> 2
 \  /
  3

If the implementation created a fresh clone every time a node was encountered, the cloned graph would incorrectly contain duplicate versions of node 3.

The hash map guarantees one-to-one correspondence between original and cloned nodes, preserving the graph structure exactly.