Deep copy a connected undirected graph using DFS with a hash map to track original-to-clone node mapping

Clone Graph

Problem

Build systems often need to snapshot in-memory object graphs for undo history or inter-process transfer. Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Each node has an integer value and a list of neighbors.

Example 1:

Input: adjList = [[2,5],[1,3],[2,4],[3,5],[4,1]]
Output: [[2,5],[1,3],[2,4],[3,5],[4,1]]
Explanation: a deep copy - same structure and values, but every node in the output is a new object with no reference to any original node.

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: a single node with no neighbors clones to one new node with an empty neighbor list.

Example 3:

Input: adjList = []
Output: []
Explanation: an empty graph returns null.

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 50
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The graph is connected and all nodes can be visited starting from the given node.

Try it

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

def clone_graph(node: Node) -> Node:
    pass

Tests

def build_graph(edges, n):
    nodes = [Node(i) for i in range(1, n + 1)]
    for u, v in edges:
        nodes[u-1].neighbors.append(nodes[v-1])
        nodes[v-1].neighbors.append(nodes[u-1])
    return nodes

def is_deep_copy(original, cloned, visited=None):
    if visited is None:
        visited = set()
    if original is None and cloned is None:
        return True
    if original is cloned:
        return False
    if original.val != cloned.val:
        return False
    visited.add(id(original))
    orig_vals = sorted(n.val for n in original.neighbors)
    clone_vals = sorted(n.val for n in cloned.neighbors)
    return orig_vals == clone_vals

nodes = build_graph([(1,2),(2,3),(3,4),(4,5),(5,1)], 5)
result = clone_graph(nodes[0])
assert result is not None and result is not nodes[0], "returns new node"
assert is_deep_copy(nodes[0], result), "structure matches"
assert clone_graph(None) is None, "handles None input"
single = Node(1)
cloned_single = clone_graph(single)
assert cloned_single is not single and cloned_single.val==1, "single node"
assert cloned_single.neighbors==[], "single node no neighbors"

Hints (3)

Solution Breakdown

Approach: DFS with an original-to-clone hash map (visited map that doubles as the clone registry).

The visited dict maps every original node to its freshly minted clone, and it carries two jobs at once - it is the cycle guard and the lookup table that lets shared neighbors point at the same clone object. dfs(original) first checks the map: if original is already there, the clone exists, so return it immediately instead of recursing. Otherwise create the clone, and - this is the critical ordering - register it in the map before touching any neighbor. Only then loop over original.neighbors, recursing into each and appending the returned clones to clone.neighbors. Registering before recursing is what defeats cycles: when a neighbor's recursion eventually loops back to the current node, the map lookup at the top fires and returns the in-progress clone rather than spinning forever. Trace the 5-cycle 1-2-3-4-5-1: cloning 1 registers clone-1, recurses through 2, 3, 4, 5, and when 5 recurses back to 1 the map already holds clone-1, so the back-edge resolves and the recursion unwinds cleanly.

Edge cases: A None input returns None via the if not node guard. A single isolated node clones to a fresh node with an empty neighbor list - the loop body never runs.

Complexity: O(V + E) time, O(V) space - every node is created once and every edge is walked once; the map plus recursion stack are both O(V).

Clone Graph

Problem

Solution Breakdown

Discussion