Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 133. Clone Graph

Asked at:

DESCRIPTION

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value (val) and a list of its neighbors (neighbors). The clone must preserve the graph's structure, including cycles and shared neighbors, ensuring each original node maps to exactly one unique cloned node. For example, if node 1 connects to nodes 2 and 3, and node 2 also connects to node 3, the cloned graph must maintain these exact relationships.

Input:

adjList = [[2,4],[1,3],[2,4],[1,3]]
Node 1 connects to nodes 2 and 4
Node 2 connects to nodes 1 and 3
Node 3 connects to nodes 2 and 4
Node 4 connects to nodes 1 and 3

Output:

A cloned graph with the same structure:
Cloned node 1 connects to cloned nodes 2 and 4
Cloned node 2 connects to cloned nodes 1 and 3
Cloned node 3 connects to cloned nodes 2 and 4
Cloned node 4 connects to cloned nodes 1 and 3

Explanation: Each node in the original graph has a corresponding clone with identical neighbor relationships preserved

Constraints:

The number of nodes in the graph is in the range [0, 100]
Node values are unique: 1 <= Node.val <= 100
The graph is connected (all nodes are reachable from the given node)
The graph is undirected (if node A connects to node B, then node B connects to node A)
There are no self-loops or duplicate edges

Understanding the Problem

The core challenge is avoiding duplicate clones when traversing a graph with cycles and shared neighbors. If we naively clone each neighbor recursively, we'll create multiple copies of the same node and enter infinite loops on cycles. We need a mapping structure to track which original nodes have already been cloned, ensuring each node is cloned exactly once. The solution requires graph traversal (DFS or BFS) combined with a hash map to store the original-to-clone correspondence.

Building Intuition

A naive recursive approach would clone each node and recursively clone its neighbors, but this fails on cycles (infinite recursion) and shared neighbors (duplicate clones). The key insight is to use a hash map to track cloned nodes: before cloning a neighbor, check if it's already been cloned. If yes, reuse the existing clone; if no, create a new clone and add it to the map. For example, when cloning a square graph (1-2-3-4-1), after cloning node 1 and its neighbor node 2, when we later encounter node 1 as a neighbor of node 4, we retrieve the existing clone from the map instead of creating a duplicate.

Graph cloning is fundamental in serialization/deserialization systems, state management (creating snapshots of complex object graphs), and distributed systems (replicating data structures across nodes). Understanding how to preserve object identity and relationships during deep copying is crucial for implementing copy-on-write semantics, undo/redo functionality, and graph databases.

Common Pitfalls

Forgetting to handle null input: Always check if the input node is null before starting traversal

Creating duplicate clones: Without a visited map, shared neighbors get cloned multiple times, breaking the graph structure

Infinite recursion on cycles: Failing to check if a node is already cloned causes stack overflow on cyclic graphs

Cloning neighbors before adding to map: The current node must be added to the map before recursively cloning neighbors to handle back-edges correctly

Implementation

DFS Traversal with Clone Mapping

Implement a recursive depth-first search that clones nodes while maintaining a HashMap<Node, Node> to map original nodes to their clones. For each node, create its clone immediately and store it in the map before processing neighbors (this prevents infinite recursion on cycles). Then recursively clone each neighbor, checking the map first to reuse existing clones. For example, when cloning a triangle graph (1-2-3-1), after cloning node 1 and recursively cloning neighbor 2, when node 2 tries to clone neighbor 1, it finds the existing clone in the map and reuses it.

Solution

def cloneGraph(node, clone_map=None):
    if not node:
        return None
    if clone_map is None:
        clone_map = {}
    if node in clone_map:
        return clone_map[node]
    
    clone = Node(node.val)
    clone_map[node] = clone
    
    for neighbor in node.neighbors:
        clone.neighbors.append(cloneGraph(neighbor, clone_map))
    
    return clone

BFS Traversal Alternative

Implement an iterative breadth-first search using a Queue for level-order traversal and the same clone mapping strategy from the DFS approach. Start by cloning the input node and adding it to both the queue and the map. For each node dequeued, iterate through its neighbors: if a neighbor hasn't been cloned yet, create its clone, add to the map, and enqueue it for later processing. Then connect the current clone to each neighbor's clone. For example, in a star graph (center node connected to 4 leaf nodes), the BFS processes the center first, clones all leaves in one pass, then connects them without revisiting any node.

Solution

from collections import deque
def cloneGraphBFS(node):
    if not node:
        return None
    
    clone_map = {node: Node(node.val)}
    queue = deque([node])
    
    while queue:
        current = queue.popleft()
        
        for neighbor in current.neighbors:
            if neighbor not in clone_map:
                clone_map[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            
            clone_map[current].neighbors.append(clone_map[neighbor])
    
    return clone_map[node]

Complete Integration

Combine both traversal approaches into a unified solution interface that demonstrates when to use each method. The DFS approach (Section 1) is more memory-efficient for deep graphs due to implicit stack usage, while the BFS approach (Section 2) is better for shallow, wide graphs and provides level-order processing. Show a wrapper that selects the appropriate strategy based on graph characteristics, or provides both as alternative implementations. For example, create a GraphCloner class that exposes both cloneDFS(node) and cloneBFS(node) methods, allowing users to choose based on their specific graph structure and memory constraints.

Solution

class GraphCloner:
    def __init__(self):
        pass
    
    def cloneDFS(self, node):
        """Memory-efficient for deep graphs"""
        return cloneGraph(node)
    
    def cloneBFS(self, node):
        """Better for shallow, wide graphs"""
        return cloneGraphBFS(node)
    
    def clone(self, node, prefer_bfs=False):
        """Auto-select strategy based on preference"""
        return self.cloneBFS(node) if prefer_bfs else self.cloneDFS(node)

What We've Learned

Pattern: Use a hash map to track visited nodes during graph traversal to prevent duplicate processing and handle cycles
Use Case: Apply this clone mapping technique to deep copy any object graph with circular references (linked lists with cycles, tree parent pointers, bidirectional relationships)
Trade-off: DFS uses less memory (implicit call stack) but risks stack overflow on deep graphs; BFS uses explicit queue but handles deep graphs safely
Critical Step: Always add node to visited map before processing neighbors to correctly handle back-edges and self-references

Problems to Practice

Copy Graph

easy

Depth-First Search

This is essentially the same problem as Clone Graph (LeetCode 133). It requires creating a deep copy of a graph while preserving all connections and handling cycles, using DFS traversal with a hash map to track visited nodes.

Practice

Adjacency List

Lesson

Depth-First Search

This lesson covers graph representation using adjacency lists, which is the fundamental data structure used in the Clone Graph problem. Understanding how graphs are represented is essential for solving graph cloning problems.

Learn

Graph Valid Tree

medium

Depth-First Search

This problem also involves graph traversal with cycle detection and uses similar techniques of tracking visited nodes during DFS. It reinforces understanding of graph connectivity and traversal patterns needed for cloning graphs.

Practice

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid December, 2025

Junior

Late November, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 133. Clone Graph

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

DFS Traversal with Clone Mapping

BFS Traversal Alternative

Complete Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact