Clone Graph

Problem Description

Given a reference to 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 (List[Node]) of its neighbors.

Examples

Constraints

• The number of nodes in the graph is in the range [0, 100].
• 1 ≤ Node.val ≤ 100
• Each node’s value is unique.
• The graph is undirected and connected.

Mapping Old Nodes to Clones During Traversal

A deep copy means creating entirely new objects in memory that mirror the original graph structure. If we simply copy a node and its neighbors recursively without tracking visited nodes, we will fall into an infinite loop because undirected graphs contain cycles (e.g., node 1 connects to node 2, which connects back to node 1).

To prevent cycles and preserve identical sharing of nodes, we use a hash map that maps original_node -> cloned_node.

• When visiting a node, check if its clone already exists in the map.
• If it exists, return the cloned node reference.
• If not, create a new clone of the node, insert the pair into our map, and then recursively clone and append all its neighbors to the clone’s neighbor list.

Solution 1: Recursive DFS with Clone Mapping

Use a hash map to track visited nodes and their corresponding cloned instances during a DFS traversal.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Node, Node> clones = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;

        // if clone already exists, return it to prevent cycle
        if (clones.containsKey(node)) {
            return clones.get(node);
        }

        // create clone node
        Node clone = new Node(node.val, new ArrayList<>());
        clones.put(node, clone);

        // recursively clone neighbors
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }

        return clone;
    }
}

class Solution:
    def __init__(self):
        self.clones = {}

    def cloneGraph(self, node: "Node") -> "Node":
        if not node:
            return None

        # if clone already exists, return it to prevent cycle
        if node in self.clones:
            return self.clones[node]

        # create clone node
        clone = Node(node.val)
        self.clones[node] = clone

        # recursively clone neighbors
        for neighbor in node.neighbors:
            clone.neighbors.append(self.cloneGraph(neighbor))

        return clone

#include <unordered_map>
#include <vector>

class Solution {
private:
    std::unordered_map<Node*, Node*> clones;

public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        // if clone already exists, return it to prevent cycle
        if (clones.count(node)) {
            return clones[node];
        }

        // create clone node
        Node* clone = new Node(node->val);
        clones[node] = clone;

        // recursively clone neighbors
        for (Node* neighbor : node->neighbors) {
            clone->neighbors.push_back(cloneGraph(neighbor));
        }

        return clone;
    }
};

Complexity Analysis:

• Time Complexity: O(V + E) where V is the number of vertices (nodes) and E is the number of edges. We visit each node and traverse each edge once.
• Space Complexity: O(V) to store the mapping of V nodes in the hash map, plus O(H) recursion stack space where H is the graph depth.

Where it breaks: Nothing breaks for standard graph cases. If the graph contains millions of nodes, the recursion stack depth can become a bottleneck, requiring an iterative BFS approach using a queue.

Common Mistakes

• Not putting the clone into the map before recursing on neighbors. If you call cloneGraph on neighbors before adding the current clone to the map, a cycle in the graph will trigger infinite recursion and cause a stack overflow.
• Making a shallow copy of neighbor lists. Doing clone.neighbors = node.neighbors copies pointers to the original nodes, which violates the deep copy requirement.
• Not handling the null node input. If the graph is empty, your code must return null immediately instead of dereferencing values.

Frequently Asked Questions

Can we solve this iteratively using BFS? Yes. You can use a queue and a hash map. Initialize by pushing the start node into the queue and adding its clone to the map. Then, while the queue is not empty, pop a node, iterate over its neighbors, clone them if they are not in the map (and push them to the queue), and append their clones to the popped node’s clone neighbor list.

How does this handle isolated nodes? If a node has no neighbors, the neighbors loop does not execute, and the node is cloned and returned correctly.

What does this problem test in interviews? It tests your understanding of graph traversal, pointers vs objects (deep copy vs shallow copy), and using lookup structures to prevent infinite loops in cyclic graphs.

← All Problems