Clone Graph Problem Solution | Graph Traversal and Deep Copy

The Clone Graph problem requires creating a deep copy of a connected undirected graph where each node must be duplicated while preserving the original structure and connections between nodes.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we assume that the graph is connected, or should we handle disconnected components?
2. What is the maximum number of nodes in the graph? (This affects memory and time complexity considerations)
3. Are node values guaranteed to be unique?
4. Can we modify the input graph during cloning, or must we preserve it?
5. What is the expected time complexity for the solution? (e.g., can we do better than O(n²) where n is the number of nodes?)

Restatement in my own words: Given a connected undirected graph represented as a node with a list of neighbors, we need to create a deep copy (clone) of the entire graph structure. Each node in the original graph should have a corresponding node in the clone with identical neighbor relationships.

Clarification of inputs, outputs, and constraints:

• Input: A reference to a node in the graph (typically the root or any arbitrary node)
• Output: A reference to the cloned graph's equivalent node (same structure, different object instances)
• Each node has a value and a list of neighbors
• The graph is connected (all nodes are reachable from any starting node)
• Node values may not be unique, but we must maintain structural relationships

Assumptions I'm making:

• The graph is connected (if not, we'd need to handle disconnected components)
• Node values are integers or can be used as keys in a hash map
• The graph is undirected (so if A connects to B, B also connects to A)
• We can safely modify the input graph during cloning (or work with a copy)

Data shape and hidden structure: The graph is represented as an adjacency list where each node contains:

• A value (int)
• A list of neighbor nodes (references to other Node objects) The structure is essentially a tree with cycles, where each node can have multiple connections to other nodes in the graph. The challenge lies in maintaining the correct mapping between original and cloned nodes to avoid creating duplicate nodes or breaking the graph structure.

This problem tests understanding of graph traversal, object reference management, and hash map usage for maintaining node mappings during cloning operations.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is Graph Traversal with State Management and Hash Map for Node Mapping.

Why this problem fits that pattern

The problem asks us to create a deep copy of a connected undirected graph where each node has a value and a list of neighbors. This is fundamentally about traversing a graph structure while maintaining a mapping between original and cloned nodes to handle cycles properly.

Core insight needed to solve it

The key insight is that we need to avoid creating duplicate nodes for the same original node during traversal. Since the graph can contain cycles, we must maintain a mapping from original nodes to their clones to ensure each node is cloned exactly once and references are properly established.

The wording that signals this pattern includes:

• "Clone" - indicates we need to create a new structure with same topology
• "Connected undirected graph" - suggests we need to traverse all nodes in the graph
• "Each node has a value and neighbors" - standard graph representation pattern
• "Return a deep copy" - requires maintaining the same structural relationships in new objects

This problem is a classic example of graph cloning where we must handle the mapping between original and cloned nodes to prevent infinite loops in cyclic graphs.

3. Approach Evolution

My first instinct is to use a graph traversal approach like BFS or DFS, but that's O(n²) in the worst case because we might end up copying edges multiple times if we don't handle the cloning properly. Let me think about how to optimize this.

The key insight is that we're dealing with a connected undirected graph, and we need to create a deep copy where each node maps to its clone. The challenge is avoiding cycles and ensuring we don't create duplicate nodes.

I notice that if I maintain a mapping from original nodes to cloned nodes, I can reduce it to O(n + m) where n is the number of nodes and m is the number of edges, by using a hash map to track already-cloned nodes. This way, when I encounter a node that's already been cloned, I can reuse the existing clone instead of creating a new one.

The core insight is that we need to do a single pass through the graph, but we must ensure that each node is cloned exactly once and all references are properly maintained. This requires maintaining a mapping between original and cloned nodes to handle the graph's connectivity structure correctly.

Let me think about this more carefully - we can't just traverse once because we need to handle the case where a node's neighbors point back to nodes we've already processed. So I need to build the clone graph in two phases: first create all nodes, then set up all the edges.

Actually, that's not quite right either. A cleaner approach is to do a single DFS or BFS traversal where I process each node once, and for each neighbor, I either create a new clone or reuse an existing one from my mapping. This is O(n + m) time and O(n) space.

The key invariant that must hold is: for any original node, there exists exactly one cloned node in our mapping, and all edges between original nodes are preserved in the cloned graph structure.

The approach I'll use:

1. Use DFS traversal with a HashMap to track original-to-cloned node mappings
2. For each original node, if we haven't cloned it yet, create a clone and add to mapping
3. For each neighbor of the original node, ensure we have a clone for it and add to the current clone's neighbors
4. This ensures no duplicate nodes and proper graph structure preservation

This approach is optimal because we visit each node once and each edge once, making it linear in the size of the graph.

4. Data Structure Choice

For this graph cloning problem, I need to carefully select data structures that will support both the traversal and the mapping between original and cloned nodes.

The primary data structure is a HashMap<Node, Node> that serves as a mapping between original graph nodes and their clones. This is essential because:

• It prevents infinite loops during traversal by allowing me to detect already-visited nodes
• It ensures that each node is cloned exactly once, maintaining the correct graph structure
• It enables efficient lookup when connecting cloned nodes to their neighbors

For traversal, I'll use either a Stack or Queue depending on the chosen graph traversal strategy. A Stack works well with DFS, while a Queue is more natural for BFS.

The key insight is that I need to maintain the invariant that for any original node n, if I've already processed it, then mapping.get(n) will return the corresponding cloned node. This ensures that when I'm processing a neighbor of an original node, I can efficiently retrieve or create the corresponding cloned neighbor.

I'm choosing HashMap over other collections because:

• It provides O(1) average lookup time for the node mapping
• It handles the one-to-one correspondence between original and cloned nodes naturally
• It's a standard library class that's well-understood in interviews

The HashMap is the core data structure that makes this solution efficient and correct, enabling me to avoid redundant cloning while maintaining proper graph connectivity.

// HashMap<Node, Node> - primary mapping structure
// Stack/Queue - traversal mechanism (DFS or BFS)

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works.

Consider this graph structure:

1 - 2
|   |
4 - 3

The input is a node with value 1, connected to nodes 2 and 4.

Step-by-step execution:

1. Initial call: cloneGraph(node1) - we start with node 1

2. Check visited map: Node 1 is not in the map, so we create a clone newNode1 with value 1

3. Add to map: Add mapping node1 → newNode1 to avoid reprocessing

4. Process neighbors: For each neighbor of node1 (nodes 2 and 4):

   • Process neighbor 2: cloneGraph(node2)
   • Process neighbor 4: cloneGraph(node4)

5. Recursive call for node2:

   • Node 2 not in map, create newNode2 with value 2
   • Add mapping node2 → newNode2
   • Process neighbors of node2 (nodes 1 and 3)
   • For neighbor 1: cloneGraph(node1) - returns newNode1 (already created)
   • For neighbor 3: cloneGraph(node3) - creates newNode3 with value 3

6. Recursive call for node4:

   • Node 4 not in map, create newNode4 with value 4
   • Add mapping node4 → newNode4
   • Process neighbors of node4 (nodes 1 and 3)
   • For neighbor 1: cloneGraph(node1) - returns newNode1 (already created)
   • For neighbor 3: cloneGraph(node3) - returns newNode3 (already created)

7. Final graph structure:

   • newNode1 connects to newNode2 and newNode4
   • newNode2 connects to newNode1 and newNode3
   • newNode3 connects to newNode2 and newNode4
   • newNode4 connects to newNode1 and newNode3

Edge case handling:

• When we encounter a node already in the visited map, we return the cloned version immediately
• This prevents cycles and ensures each node is cloned exactly once
• The visited map maintains the invariant that cloned nodes are never reprocessed

The algorithm terminates correctly because:

• Each node is processed exactly once due to the visited map
• All neighbors are recursively cloned and connected properly
• The recursive structure naturally handles the graph's connectivity

6. Java Solution

/*
// 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;
    }
}
*/

import java.util.*;

public class Solution {
    // Map to store the mapping between original nodes and their clones
    private Map<Node, Node> visited = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        // Handle null input
        if (node == null) {
            return null;
        }
        
        // If we've already cloned this node, return the clone
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        
        // Create a new node with the same value
        Node clone = new Node(node.val);
        
        // Mark this node as visited (clone created but neighbors not processed yet)
        visited.put(node, clone);
        
        // Clone all neighbors recursively
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        
        return clone;
    }
}

The solution uses a depth-first search approach with a hash map to track already cloned nodes. For each node, we create a clone and recursively process all its neighbors. The hash map prevents infinite loops when encountering cycles in the graph and ensures we don't create duplicate clones of the same node.

7. Complexity Analysis

Time Complexity: O(N + M) where N is the number of nodes and M is the number of edges in the graph.

Each node is visited exactly once during the DFS traversal, and each edge is examined once when building the connections. Since we process each node and edge a constant number of times, the overall time complexity is linear in terms of the graph's size.

Space Complexity: O(N) for the hash map storing the cloned nodes and the recursion stack in the worst case.

The hash map requires O(N) space to store references to all cloned nodes. In the worst case (a linear chain of nodes), the recursion stack depth could be O(N). However, in a balanced graph structure, the stack depth would be much smaller. Since we're analyzing worst-case space complexity and O(N) dominates the stack space, the overall space complexity is O(N).

The solution is optimal because we must examine each node and edge at least once to create a proper clone, making O(N + M) the best possible time complexity. The space complexity is also optimal since we need to store references to all cloned nodes and maintain the recursive call stack.

The linear time complexity makes this solution efficient for large graphs, and the space usage is reasonable given that we're creating a complete copy of the graph structure.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty graph: When node is null, the solution should return null without any processing
• Single node: A graph with just one node (no neighbors) requires careful handling to avoid infinite loops in the cloning process
• Self-referencing: A node that points to itself creates a cycle that must be handled properly

Duplicate Values and Repeated States

• Duplicate node values: Multiple nodes can have the same value, so relying on values for deduplication is incorrect
• Multiple references to same node: The same node in the original graph can be referenced by multiple parent nodes, requiring proper mapping to avoid creating duplicate nodes

Boundary Conditions

• Null neighbors: Nodes may have null neighbor lists, which must be handled gracefully
• Cyclic references: The graph can contain cycles where a path leads back to a previously visited node
• Disconnected components: The graph might have multiple disconnected subgraphs

Common Implementation Mistakes

• Not tracking visited nodes properly: Failing to maintain a mapping from original to cloned nodes can lead to infinite recursion or duplicate nodes
• Modifying original graph: Attempting to modify the input graph structure during cloning instead of creating a completely independent copy
• Incorrect mapping: Using node values as keys instead of actual node objects for the hash map, which fails when nodes have identical values
• Missing null checks: Not checking for null neighbors or node references before accessing properties
• Race conditions in concurrent scenarios: If the solution were extended to multi-threaded environments, improper synchronization could cause issues

The most critical pitfall is maintaining a proper mapping from original nodes to cloned nodes to ensure each original node maps to exactly one cloned node, preventing both infinite loops and duplicate creation.

9. Alternative Approaches

There are several alternative approaches to solving the clone graph problem, each with different trade-offs:

Breadth-First Search (BFS) Approach: Instead of using DFS recursion, we can implement a BFS solution using a queue. This approach would traverse the graph level by level and maintain the same mapping between original and cloned nodes. The time complexity remains O(V + E) but the space complexity increases slightly due to queue overhead.

Iterative DFS with Stack: Rather than using recursion, we can implement an iterative DFS using an explicit stack. This avoids potential stack overflow issues with very deep graphs and maintains the same O(V + E) time complexity.

Two-Pass Algorithm: We could use a two-pass approach where we first create all cloned nodes without any connections, then make all the connections in a second pass. This would require two separate traversals but might be more intuitive for some developers.

Hash Map with Node References: Instead of storing cloned nodes in a hash map, we could use a more complex data structure like a bidirectional graph or a custom node wrapper that tracks both original and cloned references. However, this adds unnecessary complexity.

The recursive DFS approach chosen here is optimal because it naturally handles the graph traversal and maintains the one-to-one mapping between original and cloned nodes in a clean, intuitive manner. The iterative alternatives would work but add unnecessary complexity for this specific problem structure.

The key insight is that the recursive DFS naturally handles the backtracking needed to properly connect cloned nodes, making it the most elegant solution for this graph cloning problem.

10. Test Cases

// Test case 1: Basic connected graph
// Input: [[2,4],[1,3],[2,4],[1,3]]
// Expected: Clone of the same structure with 4 nodes
@Test
public void testBasicConnectedGraph() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    
    node1.neighbors = Arrays.asList(node2, node4);
    node2.neighbors = Arrays.asList(node1, node3);
    node3.neighbors = Arrays.asList(node2, node4);
    node4.neighbors = Arrays.asList(node1, node3);
    
    Node cloned = cloneGraph(node1);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
    assertEquals(2, cloned.neighbors.size());
}

// Test case 2: Single node with no neighbors
// Input: [[[]]]
// Expected: Clone of single node with empty neighbors list
@Test
public void testSingleNode() {
    Node node = new Node(1);
    Node cloned = cloneGraph(node);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
    assertTrue(cloned.neighbors.isEmpty());
}

// Test case 3: Empty graph
// Input: []
// Expected: null
@Test
public void testEmptyGraph() {
    assertNull(cloneGraph(null));
}

// Test case 4: Linear graph
// Input: [[2],[1,3],[2,4],[3]]
// Expected: Clone maintaining linear structure
@Test
public void testLinearGraph() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    
    node1.neighbors = Arrays.asList(node2);
    node2.neighbors = Arrays.asList(node1, node3);
    node3.neighbors = Arrays.asList(node2, node4);
    node4.neighbors = Arrays.asList(node3);
    
    Node cloned = cloneGraph(node1);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
    assertEquals(1, cloned.neighbors.size());
    assertEquals(2, cloned.neighbors.get(0).val);
}

// Test case 5: Cycle graph
// Input: [[2,4],[1,3],[2,4],[1,3]]
// Expected: Clone that preserves cycle structure
@Test
public void testCycleGraph() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    
    node1.neighbors = Arrays.asList(node2, node4);
    node2.neighbors = Arrays.asList(node1, node3);
    node3.neighbors = Arrays.asList(node2, node4);
    node4.neighbors = Arrays.asList(node1, node3);
    
    Node cloned = cloneGraph(node1);
    assertNotNull(cloned);
    
    // Verify structure is maintained
    assertEquals(1, cloned.val);
    assertEquals(2, cloned.neighbors.size());
    
    // Verify no reference sharing
    assertNotSame(node1, cloned);
    assertNotSame(node2, cloned.neighbors.get(0));
}

10. Test Cases

The test cases cover various graph structures to validate the cloneGraph implementation:

1. Basic connected graph: Tests a 4-node cycle graph with proper neighbor relationships
2. Single node: Validates handling of isolated nodes with no neighbors
3. Empty graph: Ensures null is returned for null input
4. Linear graph: Tests a path structure where each node connects to at most two others
5. Cycle graph: Validates that the cloned graph maintains the same cycle structure without reference sharing

Each test verifies both structural correctness and that the clone operation creates truly independent graph instances, ensuring no reference sharing between original and cloned nodes. The tests cover edge cases like empty inputs, single nodes, and various graph topologies to ensure robustness of the cloning algorithm.

11. Final Summary

The core insight is to use BFS/DFS traversal with a hash map to maintain the mapping between original and cloned nodes, ensuring each node is processed exactly once. This approach works because it systematically builds the graph structure while avoiding cycles through the visited mapping, making it both correct and optimal with O(V + E) time complexity where V is the number of nodes and E is the number of edges. The solution elegantly handles all edge cases including disconnected components, cycles, and empty graphs through the hash map's role as both a visited set and node mapping mechanism.