Clone Graph
Last Updated: April 4, 2026
Understanding the Problem
At first glance, this looks straightforward. You're given a graph node, and you need to make a complete copy of the entire graph structure. But the tricky part is that graphs can have cycles. If node 1 points to node 2, and node 2 points back to node 1, a naive recursive copy would loop forever.
So the real challenge isn't the copying itself. It's tracking which nodes you've already cloned so you don't create duplicates or get stuck in infinite loops. Every time you encounter a node, you need to answer one question: have I already cloned this node? If yes, return the existing clone. If no, create a new clone and then recursively (or iteratively) clone its neighbors.
The key insight is that a hash map from original node to cloned node serves double duty. It acts as both a "visited" set (preventing infinite loops) and a lookup table (so you can wire up neighbor references correctly).
Key Constraints:
0 <= number of nodes <= 100— Very small graph. Even O(n^2) or O(n^3) would work, but we should still aim for optimal O(V + E) since that's the natural complexity of graph traversal.1 <= Node.val <= 100and values are unique — We could use the value as a key, but using the node reference itself as a hash map key is cleaner and more general.- No repeated edges, no self-loops — We don't need to worry about degenerate edge cases in the graph structure itself.
- The graph is connected — Starting from the given node, we can reach every node. No need to handle disconnected components.
Approach 1: BFS with Hash Map
Intuition
The most natural iterative approach. Start from the given node, create its clone, and use a queue to process nodes level by level. The hash map serves as both a visited tracker and a lookup for already-cloned nodes.
Here's the thought process: when we dequeue a node, we iterate through its neighbors. For each neighbor, if we haven't cloned it yet, we create the clone and enqueue it. Either way, we add the cloned neighbor to the current clone's neighbor list. By the time the queue is empty, every node has been cloned and every neighbor relationship has been wired up.
Algorithm
- If the input node is
null, returnnull. - Create a hash map to store the mapping from original nodes to cloned nodes.
- Clone the starting node (with an empty neighbor list) and add it to the map.
- Add the starting node to a queue.
- While the queue is not empty, dequeue a node.
- 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.
- Return the clone of the starting node from the map.
Example Walkthrough
Code
- Time Complexity: O(V + E). We visit each node exactly once and process each edge twice (once from each direction in an undirected graph).
- Space Complexity: O(V). The hash map stores one entry per node. The queue holds at most O(V) nodes.
Both BFS and DFS achieve the same O(V + E) time, but the recursive DFS approach is often more concise and elegant. What if we let the call stack handle the traversal instead of managing a queue?
Approach 2: DFS with Hash Map (Recursive)
Intuition
The recursive DFS approach is functionally identical to BFS in terms of correctness and complexity, but many find it more elegant. The recursion naturally handles the "visit neighbors" logic without an explicit queue.
The idea is simple: to clone a node, first check if we've already cloned it (base case). If so, return the existing clone. Otherwise, create a new clone, add it to the map immediately (this is critical to prevent infinite loops), and then recursively clone each neighbor and add them to the clone's neighbor list.
The order of operations is what prevents infinite loops. We add the clone to the map before recursing into neighbors. When a cycle brings us back to a node we've already started cloning, the map lookup catches it and returns the existing clone instead of recursing infinitely. This is the same principle as marking nodes "visited" in standard graph DFS.
Algorithm
- If the input node is
null, returnnull. - If the node is already in the hash map, return its clone (this handles cycles).
- Create a new clone of the current node with an empty neighbor list.
- Add the mapping from original to clone in the hash map.
- For each neighbor of the original node, recursively clone it and add the result to the clone's neighbor list.
- Return the clone.
Example Walkthrough
Code
- Time Complexity: O(V + E). Each node is visited once, and each edge is processed once from each direction.
- Space Complexity: O(V). The hash map stores V entries. The recursion stack can go as deep as V in the worst case (a long chain graph).