LeetCode 133: Clone Graph

Problem Restatement

We are given a reference to a node in a connected undirected graph.

Each node has:

We need to return a deep copy of the graph.

A deep copy means:

1. Every original node gets a new node object.
2. Every edge is copied between the new node objects.
3. No cloned node should point back to an original node.

If the input node is None, return None.

LeetCode represents test cases using an adjacency list. The given node is the node with val = 1, and each node value is unique. The graph is connected, has no repeated edges, and has no self-loops.

Examples

Example 1:

adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]

This means:

The cloned graph should have the same structure:

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

But the nodes must be new objects.

Example 2:

adjList = [[]]

There is one node with value 1, and it has no neighbors.

The clone is also one node with value 1 and no neighbors.

Example 3:

adjList = []

There are no nodes.

The input node is None, so the output is also None.

Input and Output

Function shape:

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        ...

First Thought: Copy the Current Node and Its Neighbors

A natural first idea is:

1. Create a new node with the same value.
2. For each neighbor, create a new neighbor node.
3. Continue recursively.

This fails when the graph has cycles.

For example:

1 -- 2

Node 1 points to node 2.

Node 2 points back to node 1.

If we clone recursively without remembering visited nodes, we get:

clone 1
  clone 2
    clone 1
      clone 2
        ...

This never ends.

We need a way to remember which original nodes have already been cloned.

Key Insight

Use a hash map:

old_to_new = {}

The key is an original node.

The value is its cloned node.

original node -> cloned node

This map solves two problems:

1. It prevents infinite recursion in cyclic graphs.
2. It ensures every original node corresponds to exactly one cloned node.

The important step is to insert a node into the map immediately after creating its clone, before cloning its neighbors.

That way, if the graph points back to the same node, we can return the clone that already exists.

DFS Algorithm

Define a helper:

dfs(node)

It returns the cloned version of node.

For each call:

1. If node is None, return None.
2. If node already exists in old_to_new, return the existing clone.
3. Create a new node with the same value.
4. Store it in old_to_new.
5. Recursively clone every neighbor.
6. Append cloned neighbors to the new node.
7. Return the cloned node.

Correctness

Every time DFS sees an original node for the first time, it creates exactly one cloned node with the same value and stores the mapping.

If DFS later reaches the same original node again through another path, it returns the already-created clone. Therefore, each original node maps to one unique cloned node.

For every original edge from node to neighbor, the algorithm appends dfs(neighbor) to the cloned node’s neighbor list. Since dfs(neighbor) returns the cloned version of neighbor, every original edge is reproduced between cloned nodes.

The graph is connected, so starting from the given node reaches every node in the graph. Therefore, the algorithm clones every node and every neighbor relationship reachable from the input node.

The returned node is the cloned version of the input node, and the whole reachable graph is a deep copy.

Complexity

Let:

Each node is cloned once.

Each neighbor reference is processed once. In an undirected graph, every edge appears in two neighbor lists.

Implementation

# 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 []

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        old_to_new = {}

        def dfs(curr: "Node") -> "Node":
            if curr is None:
                return None

            if curr in old_to_new:
                return old_to_new[curr]

            clone = Node(curr.val)
            old_to_new[curr] = clone

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

            return clone

        return dfs(node)

Code Explanation

The map stores original-to-clone relationships:

old_to_new = {}

When the helper receives None, it returns None:

if curr is None:
    return None

This handles the empty graph case.

If the current node has already been cloned, return its clone:

if curr in old_to_new:
    return old_to_new[curr]

This prevents infinite recursion and duplicate cloned nodes.

Create the clone:

clone = Node(curr.val)

Store it immediately:

old_to_new[curr] = clone

This timing matters. In a cycle, a neighbor may point back to this node. Because the clone is already in the map, the recursive call can reuse it.

Then clone all neighbors:

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

Each appended neighbor is a cloned node, not an original node.

Finally:

return dfs(node)

returns the cloned version of the input node.

Iterative BFS Version

DFS is concise. BFS also works.

BFS first creates the clone for the starting node, then walks through the graph with a queue.

from collections import deque

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        if node is None:
            return None

        old_to_new = {node: Node(node.val)}
        queue = deque([node])

        while queue:
            curr = queue.popleft()

            for neighbor in curr.neighbors:
                if neighbor not in old_to_new:
                    old_to_new[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)

                old_to_new[curr].neighbors.append(old_to_new[neighbor])

        return old_to_new[node]

This version avoids recursion depth concerns.

Testing

LeetCode provides the Node class and graph serializer. For local testing, we can build a small graph manually.

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

def serialize(node: Node | None) -> list[list[int]]:
    if node is None:
        return []

    seen = {}
    queue = [node]
    seen[node] = True
    nodes = []

    while queue:
        curr = queue.pop(0)
        nodes.append(curr)

        for neighbor in curr.neighbors:
            if neighbor not in seen:
                seen[neighbor] = True
                queue.append(neighbor)

    nodes.sort(key=lambda x: x.val)

    return [
        sorted(neighbor.val for neighbor in curr.neighbors)
        for curr in nodes
    ]

def run_tests():
    s = Solution()

    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 = s.cloneGraph(n1)

    assert serialize(clone) == [[2, 4], [1, 3], [2, 4], [1, 3]]
    assert clone is not n1
    assert clone.neighbors[0] is not n2

    single = Node(1)
    single_clone = s.cloneGraph(single)

    assert serialize(single_clone) == [[]]
    assert single_clone is not single

    assert s.cloneGraph(None) is None

    print("all tests passed")

run_tests()

Test meaning: