Clone Graph

Difficulty: Medium Source: NeetCode

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list of its neighbors (List[Node]).

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

Example 1: Input: adjList = [[2,4],[1,3],[2,4],[1,3]] (node 1 connects to 2 and 4, etc.) Output: A deep copy of the same graph

Example 2: Input: adjList = [[]] Output: A single node with no neighbors

Constraints:

• The number of nodes is in range [0, 100]
• 1 <= Node.val <= 100
• Node.val is unique for each node
• No repeated edges and no self-loops
• The graph is connected

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS / BFS — traversing all nodes in the graph
• Hash Maps — mapping original nodes to their clones to handle cycles

1. DFS with Hash Map

Intuition

The tricky part is cycles — if node A and node B are neighbors, cloning A means cloning B, which means cloning A again… infinite loop. The fix is a hash map that tracks {original_node → cloned_node}. Before recursing, store the clone in the map. When you encounter a node already in the map, return its clone immediately instead of creating another.

Algorithm

1. If node is None, return None.
2. Create a hash map visited = {}.
3. Define clone(node):
   • If node is already in visited, return visited[node].
   • Create a new node with the same value, store in visited.
   • For each neighbor, recursively clone it and add to the new node’s neighbors list.
   • Return the new node.
4. Return clone(node).

Solution

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


def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

    visited = {}

    def clone(n):
        if n in visited:
            return visited[n]
        copy = Node(n.val)
        visited[n] = copy  # store BEFORE recursing to handle cycles
        for neighbor in n.neighbors:
            copy.neighbors.append(clone(neighbor))
        return copy

    return clone(node)


# Build test graph: 1 -- 2 -- 3 -- 4 -- 1 (cycle)
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 = [n3, n1]

cloned = cloneGraph(n1)
print(cloned.val)                              # 1
print([n.val for n in cloned.neighbors])      # [2, 4]
print(cloned is n1)                            # False (deep copy)
print(cloned.neighbors[0] is n2)              # False (deep copy)

Complexity

• Time: O(V + E) — visits every node and edge once
• Space: O(V) — hash map plus recursion stack

2. BFS with Hash Map

Intuition

Same idea but iterative: use a queue for BFS traversal. When you first encounter a node, create its clone and add it to the map. When you process it from the queue, wire up its neighbors (creating clones for new neighbors as needed).

Algorithm

1. Create a clone of the starting node and put it in visited.
2. Enqueue the starting node.
3. While the queue is non-empty: dequeue node, for each neighbor:
   • If not in visited, create a clone and enqueue the original.
   • Add visited[neighbor] to visited[node].neighbors.
4. Return visited[start].

Solution

from collections import deque

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


def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

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

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

    return visited[node]


# Test
n1 = Node(1)
n2 = Node(2)
n1.neighbors = [n2]
n2.neighbors = [n1]

cloned = cloneGraph(n1)
print(cloned.val)                          # 1
print([n.val for n in cloned.neighbors])  # [2]
print(cloned is n1)                        # False
print(cloneGraph(None))                    # None

Complexity

• Time: O(V + E)
• Space: O(V) for the visited map and queue

Common Pitfalls

Storing the clone after recursing. You must store visited[n] = copy before recursing into neighbors, not after. If you recurse first, cycles cause infinite recursion since the node isn’t in visited yet when you circle back to it.

Forgetting the None check. The problem says the input can be an empty graph (no nodes). Always handle if not node: return None at the start.

Checking identity vs equality. The visited map should use object identity (the node object itself as the key), not the node’s value. Since Node.val is unique here it would work, but in general use the node object as the dict key.