AlgoMaster Logo

Clone Graph

mediumFrequency6 min readUpdated June 23, 2026

Understanding the Problem

You're given a graph node, and you need to produce a complete copy of the graph: new node objects with the same values and the same connections. The complication is that graphs can have cycles. If node 1 points to node 2, and node 2 points back to node 1, a copy routine that recurses into neighbors without any bookkeeping loops between the two forever.

Most of the work is tracking which nodes already have clones, so that the copy contains no duplicates and the traversal terminates. Each time you reach a node, one question decides what to do: does this node already have a clone? If yes, return the existing clone. If no, create one, then clone its neighbors.

A hash map from original node to cloned node covers both needs. It acts as a visited set that stops the traversal from looping, and as a lookup table for wiring each clone's neighbor references to the correct clone objects.

Key Constraints:

  • 0 <= number of nodes <= 100: The graph is small enough that even a quadratic solution would pass, but standard graph traversal gives O(V + E) anyway. The zero case means the input can be null, which both solutions check first.
  • 1 <= Node.val <= 100 and values are unique: Unique values mean the value could serve as a hash map key, but keying on the node reference itself works even when values repeat, so the solutions below use the reference.
  • No repeated edges, no self-loops: Each neighbor list contains distinct nodes other than the node itself, so parallel edges need no special handling.
  • The graph is connected: Every node is reachable from the given node, so a single traversal clones the whole graph. There are no disconnected components to find.

Approach 1: BFS with Hash Map

Intuition

Traverse the graph with BFS, cloning nodes as they are discovered. Start by cloning the given node and seeding the queue with the original.

When we dequeue a node, we iterate through its neighbors. If a neighbor has no clone yet, we create one, record it in the map, and enqueue the neighbor so its own edges get processed later. Either way, we append the cloned neighbor to the dequeued node's clone. When the queue is empty, every node has been cloned and every edge has been copied in both directions.

Algorithm

  1. If the input node is null, return null.
  2. Create a hash map to store the mapping from original nodes to cloned nodes.
  3. Clone the starting node (with an empty neighbor list) and add it to the map.
  4. Add the starting node to a queue.
  5. While the queue is not empty, dequeue a node.
  6. For each neighbor of the dequeued node:
    • If the neighbor hasn't been cloned yet, clone it and add it to the map and queue.
    • Add the cloned neighbor to the dequeued node's clone's neighbor list.
  7. Return the clone of the starting node from the map.

Example Walkthrough

The trace below runs BFS on the four-node graph from Example 1, where nodes 1 and 3 each connect to nodes 2 and 4. The second panel shows the hash map filling up as clones are created.

graph
1Start: Clone node 1, enqueue it. Map: {1->1'}
1clone243
cloneMap
1Clone node 1, add to map
1
:
1'
1/6

Code

DFS reaches the same O(V + E) bound with less bookkeeping: the call stack replaces the explicit queue.

Approach 2: DFS with Hash Map (Recursive)

Intuition

Write a function whose contract is "return the clone of this node". If the node is already in the map, return the existing clone. Otherwise, create the clone, add it to the map, then recursively clone each neighbor and append the results to the new clone's neighbor list.

The one ordering requirement is that the clone goes into the map before the recursive calls.

Algorithm

  1. If the input node is null, return null.
  2. If the node is already in the hash map, return its clone (this handles cycles).
  3. Create a new clone of the current node with an empty neighbor list.
  4. Add the mapping from original to clone in the hash map.
  5. For each neighbor of the original node, recursively clone it and add the result to the clone's neighbor list.
  6. Return the clone.

Example Walkthrough

The same graph from Example 1, cloned with DFS this time. The recursion goes deep along the path 1, 2, 3, 4 before unwinding, so the visit order differs from BFS even though the resulting copy is identical.

graph
1DFS(1): clone node 1, recurse into neighbor 2
1clone243
cloneMap
1DFS(1): create clone 1', add to map before recursing
1
:
1'
1/6

Code