Clone Graph — DSA · Engineering Playbook

Problem#

Given a reference to a node in a connected undirected graph, return a deep copy of the graph.

Examples#

4-node cycle 1 — 2 — 3 — 4 — 1 → an isomorphic deep copy.
Single node with no neighbors → a deep copy of just that node.
null → null.

Constraints#

The number of nodes is in [0, 100]. Node values are unique.

Approach#

DFS with a map<Node*, Node*> from original to clone. On visiting a node, if it’s already in the map, return its clone. Else, create the clone, register it, and recursively clone every neighbor.

Solution#

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> map;
        function<Node*(Node*)> dfs = [&](Node* u) -> Node* {
            auto it = map.find(u);
            if (it != map.end()) return it->second;
            Node* c = new Node(u->val);
            map[u] = c;
            for (Node* nb : u->neighbors) c->neighbors.push_back(dfs(nb));
            return c;
        };
        return dfs(node);
    }
};

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }
    seen := map[*Node]*Node{}
    var dfs func(u *Node) *Node
    dfs = func(u *Node) *Node {
        if c, ok := seen[u]; ok {
            return c
        }
        c := &Node{Val: u.Val}
        seen[u] = c
        for _, nb := range u.Neighbors {
            c.Neighbors = append(c.Neighbors, dfs(nb))
        }
        return c
    }
    return dfs(node)
}

from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None
        seen: dict = {}

        def dfs(u: 'Node') -> 'Node':
            if u in seen:
                return seen[u]
            c = Node(u.val)
            seen[u] = c
            for nb in u.neighbors:
                c.neighbors.append(dfs(nb))
            return c

        return dfs(node)

var cloneGraph = function(node) {
    if (!node) return null;
    const seen = new Map();
    const dfs = (u) => {
        if (seen.has(u)) return seen.get(u);
        const c = new Node(u.val);
        seen.set(u, c);
        for (const nb of u.neighbors) {
            c.neighbors.push(dfs(nb));
        }
        return c;
    };
    return dfs(node);
};

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

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        return dfs(node);
    }

    private Node dfs(Node u) {
        Node existing = seen.get(u);
        if (existing != null) return existing;
        Node c = new Node(u.val);
        seen.put(u, c);
        for (Node nb : u.neighbors) {
            c.neighbors.add(dfs(nb));
        }
        return c;
    }
}

function cloneGraph(node: Node | null): Node | null {
    if (!node) return null;
    const seen = new Map<Node, Node>();
    const dfs = (u: Node): Node => {
        const existing = seen.get(u);
        if (existing) return existing;
        const c = new Node(u.val);
        seen.set(u, c);
        for (const nb of u.neighbors) {
            c.neighbors.push(dfs(nb));
        }
        return c;
    };
    return dfs(node);
}

Editorial#

The map both detects cycles and serves as the lookup for “have we cloned this yet?”. Insert into the map before recursing into neighbors — otherwise the cycle would cause infinite recursion. Each edge is traversed twice (once from each endpoint), giving O(V + E).

Complexity#

Time: O(V + E).
Space: O(V) for the map plus recursion stack.

Concept revision#

Graph Valid Tree

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#