LeetCode 133 – Clone Graph

Clone Graph is a traversal problem where the traversal is the easy part. The whole difficulty is one hash map that has to do two jobs at once — remember what has been visited, and remember what each original node was copied to — and one line whose position decides whether the function terminates at all.

The problem

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node holds a value and a list of neighbours.

adjacency = [[2,4],[1,3],[2,4],[1,3]]

  1 --- 2          the copy must be a completely separate graph:
  |     |          same shape, same values, no shared node objects
  4 --- 3

[[]]  -> a single node with no neighbours
[]    -> null (an empty graph)

Undirected means every edge appears twice in the adjacency list, so the graph is full of two-node cycles. Any traversal that does not track what it has already seen will not terminate — the cycles are not an edge case here, they are the normal case.

The map does two jobs

The natural instinct is a visited set plus a separate original → copy map. One map does both:

cloned: Map<Node, Node>

  key present   -> already visited, AND here is its copy
  key absent    -> not visited yet

That merge is what makes the solution short. "Have I seen this node?" and "what is its clone?" are answered by the same lookup, and returning the existing clone is exactly the right thing to do when a cycle brings you back.

The line whose position matters

Node copy = new Node(node.val);
cloned.put(node, copy);          <- BEFORE recursing into neighbours
for (Node n : node.neighbors) copy.neighbors.add(dfs(n));

Register the clone before descending. With node 1 and node 2 pointing at each other, cloning 1 recurses into 2, which recurses back into 1 — and if 1 has not been recorded yet, that recursion never bottoms out.

Putting the put after the loop is the single most common way to write this wrong, and the symptom is a stack overflow rather than a wrong answer. The neighbours are filled in after registration, on an object that already exists, which is what breaks the cycle.

Java

class Solution {
    public Node cloneGraph(Node node) {
        // A fresh map per call: leaving state behind would return the previous
        // graph's copies on a second invocation.
        return dfs(node, new HashMap<>());
    }

    private Node dfs(Node node, Map<Node, Node> cloned) {
        if (node == null) return null;

        // One lookup answers both "seen it?" and "what is its copy?".
        Node existing = cloned.get(node);
        if (existing != null) return existing;

        Node copy = new Node(node.val);
        cloned.put(node, copy);            // BEFORE the recursion -- cycles

        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(dfs(neighbor, cloned));
        }

        return copy;
    }
}

Passing the map as a parameter rather than keeping it in a field avoids the reuse problem entirely — a second call gets a clean map with no reset to remember. That is worth preferring wherever the signature allows it.

node == null handles the empty graph. It is the only null check needed, since neighbours in a well-formed graph are never null.

Python

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        cloned: dict = {}

        def dfs(current):
            if current is None:
                return None
            if current in cloned:
                return cloned[current]

            copy = Node(current.val)
            cloned[current] = copy          # before recursing

            for neighbor in current.neighbors:
                copy.neighbors.append(dfs(neighbor))

            return copy

        return dfs(node)

The dictionary is keyed by node identity, which works because Node does not define __eq__ or __hash__ and so falls back to object identity. That is what you want — two distinct nodes with the same value must not collide. If the class did define value equality this would silently merge them, which is worth a sentence.

The BFS version

Same map, a queue instead of the call stack. Useful when the graph is deep enough to overflow the recursion:

    def cloneGraphBfs(self, node: "Node") -> "Node":
        from collections import deque

        if node is None:
            return None

        cloned = {node: Node(node.val)}     # register the entry point first
        queue = deque([node])

        while queue:
            current = queue.popleft()
            for neighbor in current.neighbors:
                if neighbor not in cloned:
                    cloned[neighbor] = Node(neighbor.val)   # create, then queue
                    queue.append(neighbor)
                cloned[current].neighbors.append(cloned[neighbor])

        return cloned[node]

The same ordering rule appears in a different costume: create the clone and record it before queueing, or a node reachable by two paths gets cloned twice and the copy ends up with more nodes than the original.

Complexity

Each node is cloned once and each edge is followed once from each end. The map is O(V) and unavoidable — without it the traversal does not terminate, so it is not an optimisation you could trade away.

The pattern

"Map from original to copy, registered before recursing" is the general recipe for deep-copying any structure with cycles. Copy List with Random Pointer (138) is the linked-list version and appears in this same round. Course Schedule (207) uses the same visited-map discipline for cycle detection rather than copying.

More generally: whenever a recursive function might revisit its own starting point, the fix is to record the in-progress result before you go deeper. Memoisation and cycle-breaking turn out to be the same line of code.

What the interviewer is checking

• That one map serves as both visited-set and old-to-new mapping.
• That the clone is registered before recursing, and why.
• That an undirected graph is full of cycles by construction.
• Null input, and a single node with no neighbours.
• That the copy shares no node objects with the original.
• That the map is keyed by identity, not by value.
• That you can give the BFS version when recursion depth is a concern.