Why this fails

This approach fails critically because undirected graphs often contain cycles (e.g., A connects to B, and B connects back to A).

1. Infinite Recursion: When clone(A) calls clone(B), clone(B) will see A as a neighbor and call clone(A) again. This creates an infinite loop, resulting in a Stack Overflow Error (Time Limit Exceeded or Runtime Error).
2. Duplicate Nodes: Even without infinite loops (e.g., a Diamond graph), a naive traversal without state tracking would create multiple distinct copies of the same original node every time it is reached via a different path. This violates the requirement of a graph isomorphism.

Core Insight for Clone Graph

The core difficulty in Clone Graph is handling cycles and shared neighbors. The graph is undirected, meaning if node $u$ is a neighbor of $v$, then $v$ is a neighbor of $u$.

To solve this efficiently, we need a mechanism to "remember" which nodes have already been cloned. This leads to the primary insight: Use a Hash Map.

The Hash Map serves two purposes:

1. Visited Set: It tracks which nodes from the original graph have already been processed, preventing infinite loops in cycles.
2. Lookup Table: It maps the Original Node (key) to the Cloned Node (value). If we encounter a node that is already in the map, we simply return the reference to the existing clone rather than creating a new one.

Visualizing the Process: Imagine the algorithm as a web crawler. When the recursion visits a node (e.g., Node 1), it first checks its notebook (the Hash Map). If Node 1 is not in the notebook, it creates "Clone 1", writes down 1 -> Clone 1, and then proceeds to visit Node 1's neighbors. When it eventually loops back to Node 1 via a neighbor, it checks the notebook, sees 1 -> Clone 1 exists, and simply links the edge to "Clone 1" instead of restarting the work.

Execution Flow

Let's trace the algorithm on a simple graph: 1 -- 2.

1. Call cloneGraph(Node 1):

   • Map is empty.
   • Create Clone 1.
   • Update Map: {Node 1: Clone 1}.
   • Iterate neighbors of Node 1: [Node 2].

2. Recursive Call cloneGraph(Node 2):

   • Node 2 is not in Map.
   • Create Clone 2.
   • Update Map: {Node 1: Clone 1, Node 2: Clone 2}.
   • Iterate neighbors of Node 2: [Node 1].

3. Recursive Call cloneGraph(Node 1) (from inside Node 2's context):

   • Node 1 is in Map.
   • Return Clone 1.

4. Back in cloneGraph(Node 2):

   • Add Clone 1 to Clone 2.neighbors.
   • End of neighbors.
   • Return Clone 2.

5. Back in cloneGraph(Node 1):

   • Add Clone 2 to Clone 1.neighbors.
   • End of neighbors.
   • Return Clone 1.

The result is a new graph structure Clone 1 -- Clone 2 that mirrors the original.

Proof of Correctness

The correctness relies on the invariant enforced by the Hash Map: Every node in the original connected component is instantiated exactly once.

1. Termination: Since the number of nodes $N$ is finite and we record every visited node in the map immediately, the DFS will never process the same node twice as a "new" node. This guarantees the recursion terminates.
2. Connectivity: The algorithm iterates over every neighbor of every visited node. Therefore, if edge $(u, v)$ exists in the original graph, the edge $(clone(u), clone(v))$ will be created in the cloned graph.
3. Deep Copy: We explicitly create new Node(val) for every unique key in the map, ensuring no references to the original graph persist in the returned structure.

Reference Implementation

C++ Solution for LeetCode 133

cpp
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
private:
    // Map to store mapping from original node to cloned node
    unordered_map<Node*, Node*> visited;

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

        // If the node is already visited, return the cloned instance
        if (visited.find(node) != visited.end()) {
            return visited[node];
        }

        // Create the clone for the current node
        Node* clone = new Node(node->val);
        
        // Add to map immediately to handle cycles
        visited[node] = clone;

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

        return clone;
    }
};

Java Solution for LeetCode 133

java
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    // HashMap to keep track of visited nodes and their clones
    private HashMap<Node, Node> visited = new HashMap<>();

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

        // If the node was already cloned, return the reference
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Create a new node (clone)
        Node clone = new Node(node.val);
        
        // Store the clone in the map immediately
        visited.put(node, clone);

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

        return clone;
    }
}

Python Solution for LeetCode 133

python
"""
# 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 __init__(self):
        # Dictionary to save the visited nodes. 
        # Key: Original Node, Value: Cloned Node
        self.visited = {}

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

        # If the node is already visited, return the clone from the dictionary
        if node in self.visited:
            return self.visited[node]

        # Create a new node with the value of the original node
        clone_node = Node(node.val, [])
        
        # Add to visited dictionary immediately to prevent cycles
        self.visited[node] = clone_node

        # Iterate through the neighbors to generate their clones
        if node.neighbors:
            for neighbor in node.neighbors:
                clone_node.neighbors.append(self.cloneGraph(neighbor))

        return clone_node

Can I just copy the list of neighbors directly?

Mistake: Doing clone.neighbors = new ArrayList<>(original.neighbors). Concept Gap: Shallow copy vs. Deep copy. Consequence: The new node will point to the original neighbor nodes, not the cloned neighbor nodes. Modifying the clone would corrupt the original graph structure.