Domain 2MediumCORE

Clone Graph

We are given a reference to the starting Node of an undirected connected graph and need to return its deep copy. A 'deep copy' means we must create new instances for every node in the original structure; simply copying references would result in two graphs sharing memory, which violates the requirement that they be independent copies.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search#Graph

133. Clone Graph

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Graph
FAANG asked: 1
Acceptance rate: 39.8%


Problem Breakdown

We are given a reference to the starting Node of an undirected connected graph and need to return its deep copy. A “deep copy” means we must create new instances for every node in the original structure; simply copying references would result in two graphs sharing memory, which violates the requirement that they be independent copies.

Inputs:

  • Reference to a Node object (the root of the graph).
  • Each Node has an integer value and a list of neighbor nodes.

Outputs:

  • A reference to the newly created copy of the starting node. The cloned neighbors must also be new instances, not references to original objects.

Constraints & Edge Cases:

  • Cycles/Undirected Edges: Since edges are undirected (A points to B implies B points to A), traversing from a neighbor might lead us back to an already visited node. We cannot simply recurse without tracking what we have seen, or we will enter infinite loops and re-create nodes unnecessarily.
  • Empty Graph: While constraints suggest connected graphs starting from the given node, robust code should handle cases where node is null (though typically not present in valid test inputs for this specific problem).
  • Single Node: A graph with one isolated node that has no neighbors must be handled correctly.

Intuition

If we try to clone a neighbor recursively without tracking visited nodes, the first time we encounter an edge back to a parent or previously visited sibling (common in undirected graphs), we would attempt to create another copy of that existing node again. This leads to infinite recursion and incorrect graph structure where multiple copies point to each other incorrectly.

The core insight is state management. We need a way to remember which original nodes have already been cloned so we can reuse the clone instead of creating a duplicate when traversing back-edges or cross-links in an undirected graph. A hash map (dictionary) mapping Original Node -> Cloned Node solves this efficiently.

We then perform a traversal (DFS is often more concise for graphs, BFS works equally well). For every node we visit:

  1. Create the new clone immediately and store it in our map using the original as the key.
  2. Iterate through its neighbors.
  3. If a neighbor hasn’t been cloned yet, recursively call (or push to queue) for that neighbor.

Approach

I will use Depth-First Search (DFS). I’ll maintain a visited dictionary where keys are the original nodes and values are their corresponding clones. This allows O(1) lookup time to check if we’ve already processed a node during traversal.

Steps:

  1. Handle edge case: If input node is None, return None.
  2. Initialize an empty map cloned_map.
  3. Define a helper function (or use iterative stack logic) that takes the original node and its clone reference.
  4. Inside traversal:
    • Create new Node instance for current neighbor if not in map? Actually, better to create it upon first encounter of any node during recursion entry.
    • Wait, standard pattern is: When visiting a node, check if it’s already cloned (in dict). If yes, return the existing clone immediately. This handles cycles naturally because we won’t re-create nodes for back-edges.
  5. However, since this is an undirected graph and neighbors are lists of references to original objects, when building the neighbor list for the clone, we must look up the corresponding cloned node from our map using the neighbor’s reference as a key.

Refined Algorithm:

  1. Create cloned_map = {}.
  2. Call DFS on input node.
  3. In DFS: If node in cloned_map, return it (cycle detection). Else, create new node and add to map.
  4. Iterate through original neighbors. For each neighbor, recursively call DFS. Append the returned clone to current cloned node’s list.

Complexity Analysis

  • Time: O(V+E)O(V + E) where V is number of nodes and E is edges. We visit every node exactly once (due to map check) and iterate over every edge in the adjacency lists exactly once during neighbor processing. Dictionary operations are O(1).
  • Space: O(V)O(V) for the recursion stack depth (DFS worst case line graph) or queue size, plus O(V)O(V) space for the cloned_map dictionary storing references to all nodes.

Solution

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    # Handle null input gracefully
    if not node:
        return None
    
    cloned_map = {}
    
    def dfs(original_node):
        # If we've already created a copy for this original node, reuse it.
        # This handles cycles and undirected edges naturally.
        if original_node in cloned_map:
            return cloned_map[original_node]
        
        # Create new clone instance immediately to avoid creating duplicates later
        clone = Node(original_node.val)
        cloned_map[original_node] = clone
        
        # Iterate over neighbors of the original node
        for neighbor in original_node.neighbors:
            # Recursively get or create the clone for this neighbor.
            # We append it directly because dfs returns either a new copy 
            # (if not visited) or an existing one (if already visited).
            clone.neighbors.append(dfs(neighbor))
            
        return clone

    return dfs(node)

Edge Cases Handled

  • Null Input: Returns None immediately if the reference is null.
  • Single Node with No Neighbors: The loop over neighbors does not execute, returns a single node instance correctly.
  • Cycles/Back-edges: If traversal reaches an already visited neighbor (e.g., A -> B and B -> A), dfs checks the map first. Since B is in cloned_map, it returns the existing clone of B instead of creating a new one, preventing infinite recursion or duplicate nodes.
  • Disconnected Components: While constraints state the graph is connected starting from the given node, if there were unreachable components not reachable via DFS/BFS from root (which shouldn’t happen per constraints), they would be ignored by this traversal logic as expected for “clone of this reference”.