Clone Graph

MediumGraph BFS/DFSBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given a reference to one node of a connected, undirected graph, where each node has an integer val and a list of its neighbors. Return a deep copy: the copy of the given node, with every node newly created and wired exactly like the originals. The examples write the graph as adjList, where adjList[i] lists the neighbors of the node with val i + 1 (values are 1-indexed and unique); the given node is val 1. For an empty graph you're given null; return null.

Examples

adjList = [[2,4],[1,3],[2,4],[1,3]] returns [[2,4],[1,3],[2,4],[1,3]]

adjList[i] lists the neighbors of node i + 1. You're handed node 1.

Node 1 links to 2 and 4, node 2 to 1 and 3, node 3 to 2 and 4, and node 4 to 1 and 3, forming a square. The copy has the same four links, but every node in it is a new object.

adjList = [[]] returns [[]]

The graph is a single node with val 1 and no neighbors, so the copy is one new node with an empty neighbor list.

adjList = [] returns []

The graph is empty, so the given node is null and the answer is null too.

Constraints

0 <= n <= 100
1 <= Node.val <= 100

Hints

Hint 1

When recursion revisits a node, how do you avoid creating a second copy and falling into infinite recursion?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Walk the graph with a depth-first search while keeping a map from each original node to its copy. On visiting a node, create the copy and store it in the map before touching the neighbors, then recurse on each neighbor and append the copy it returns. If a node is already in the map, return its existing copy instead of making another; that's what stops the walk from circling forever. O(V + E) time, O(V) space for the map and the recursion stack.

Time

O(V + E)

Space

O(V)

Pitfall

Storing the copy in the map only after cloning its neighbors: the walk from 1 to 2 leads back to 1 before 1 is registered, so it recurses forever. Register the copy first, then recurse.

Solutions

class Solution {
    private Map<Node, Node> seen = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (seen.containsKey(node)) return seen.get(node);
        Node copy = new Node(node.val);
        seen.put(node, copy);
        for (Node nb : node.neighbors) copy.neighbors.add(cloneGraph(nb));
        return copy;
    }
}

class Solution:
    def cloneGraph(self, node):
        seen = {}

        def dfs(n):
            if not n:
                return None
            if n in seen:
                return seen[n]
            copy = Node(n.val)
            seen[n] = copy
            for nb in n.neighbors:
                copy.neighbors.append(dfs(nb))
            return copy

        return dfs(node)