Clone Graph

1. Problem & Core Objective

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

class Node { int val; List<Node> neighbors; }

1 — 2
|   |        →  an identical graph made of entirely new nodes
4 — 3

Constraints: 0 <= nodes <= 100 · 1 <= Node.val <= 100 · values are unique · no self-loops or repeated edges · the graph is connected

What's actually being tested: handling cycles during a traversal. An undirected graph has a cycle in every edge — 1 → 2 and 2 → 1 — so a naive recursive copy loops forever. The fix is a map that doubles as the visited set, and understanding why one structure does both jobs is the point.

2. First-Principles Thought Process

Why the tree approach fails immediately

Copying a tree is straightforward: copy(node) = new Node(val, copy(left), copy(right)). The recursion terminates because trees have no cycles.

A graph does. In an undirected graph, node 1 lists 2 as a neighbour and node 2 lists 1 — so copying 1 copies 2, which copies 1, forever.

The two problems, and one structure that solves both

Problem 1 — infinite recursion. Need to know "have I already started copying this node?"

Problem 2 — forward references. When copying node 1, its neighbour 2 might not exist yet in the copy. Need to know "what is the copy of node 2?"

A Map<Node, Node> from original to copy answers both:

• map.containsKey(n) — already being copied, so stop
• map.get(n) — the copy, so wire to it

That's the same insight as Copy List With Random Pointer, but here the map isn't optional — there's no structural trick to replace it, because a general graph has no linear arrangement to weave into.

The critical ordering

The copy must be placed in the map before recursing into its neighbours:

Node copy = new Node(node.val);
map.put(node, copy);                    // BEFORE the recursion
for (Node nb : node.neighbors) copy.neighbors.add(clone(nb));

If the put came after, then copying 1 would recurse to 2, which recurses back to 1 — and 1 isn't in the map yet, so it starts again. Infinite recursion.

Registering before descending is what breaks the cycle, and it's the single most important line.

Why the copy can be incomplete when registered

At the moment map.put runs, copy.neighbors is empty. That's fine: the recursion will fill it, and anyone who looks it up meanwhile gets the correct object reference — the same object that will be fully populated by the time everything returns.

Registering an object identity before its contents are ready is exactly how cyclic structures get built.

3. Solution Paths

Approach 1 — Copy without tracking (broken, worth showing)

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Node copy = new Node(node.val);
    for (Node nb : node.neighbors) copy.neighbors.add(cloneGraph(nb));   // infinite
    return copy;
}

• Time does not terminate · Space stack overflow

Counter-questions on this approach

⭐ "Exactly where does this loop?"

cloneGraph(1) creates a copy and recurses into neighbour 2. cloneGraph(2) creates a copy and recurses into its neighbours, which include 1. cloneGraph(1) starts fresh — nothing recorded that it was already in progress — and the cycle repeats until the stack overflows.

Every undirected edge is a two-cycle, so this fails on the smallest possible graph: two connected nodes.

⭐ "Would a visited set alone fix it?"

It stops the infinite recursion, but then you can't wire the neighbours: on seeing an already-visited node you need its copy, and a set only tells you it exists.

So you'd need a set and a map from original to copy — at which point the map's key set already is the visited set. One structure, both jobs.

"What if the graph were acyclic — a DAG?"

It would terminate, but it could still copy shared nodes multiple times. A diamond A→B→D, A→C→D would produce two distinct copies of D, so the copy wouldn't be isomorphic to the original. The map is needed for correctness, not just termination.

Approach 2 — DFS with a map (optimal)

public Node cloneGraph(Node node) {
    return clone(node, new HashMap<>());
}

private Node clone(Node node, Map<Node, Node> map) {
    if (node == null) return null;
    if (map.containsKey(node)) return map.get(node);    // already copied — reuse it

    Node copy = new Node(node.val);
    map.put(node, copy);                                 // register BEFORE recursing

    for (Node nb : node.neighbors)
        copy.neighbors.add(clone(nb, map));

    return copy;
}

Trace — the square 1—2—3—4—1, starting at 1:

• Time O(V + E) · Space O(V) map, O(V) stack

Counter-questions on this approach

⭐ "Why must map.put come before the neighbour loop?"

Because the loop can reach back to this very node. If the put came after, clone(1) would recurse into 2, which recurses into 1 — and 1 is still absent from the map, so it creates another copy and recurses again. Infinite.

Registering first means the back-edge finds the in-progress copy and returns it immediately. That one line is what makes cycles terminate.

⭐ "The copy's neighbour list is empty when you register it. Isn't that a bug?"

No — what's stored is the object reference, and that reference is stable. Anyone who retrieves it gets the same object the recursion is about to fill.

By the time the top-level call returns, every list is complete. Publishing an identity before its contents are ready is precisely how cyclic structures are built; the alternative would be impossible.

⭐ "Does this depend on Node implementing equals and hashCode?"

It depends on Node not overriding them, so the map keys on object identity. That's what's wanted: two distinct nodes are different keys even if they held the same value.

Here values are unique so a Map<Integer, Node> keyed on val would also work — but it would silently break the moment values repeated. Keying on identity is the general answer. See 05.

"What's the complexity, precisely?"

Each node is created once, and each directed edge is traversed once — an undirected edge twice, once from each end. So O(V + E). Space is O(V) for the map plus O(V) for the recursion on a path-shaped graph.

"What about a null input or a single node with no neighbours?"

null returns null. A lone node creates one copy, and its empty neighbour loop runs zero times. Both fall out without special cases.

"Is the recursion depth a risk?"

At 100 nodes, no — worst case is a path graph giving 100 frames. If it were 10^5 I'd switch to BFS with an explicit queue, which is the next approach.

Approach 3 — BFS with a queue

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> map = new HashMap<>();
    map.put(node, new Node(node.val));

    Queue<Node> q = new ArrayDeque<>();
    q.offer(node);

    while (!q.isEmpty()) {
        Node cur = q.poll();
        for (Node nb : cur.neighbors) {
            if (!map.containsKey(nb)) {                  // first sighting
                map.put(nb, new Node(nb.val));
                q.offer(nb);
            }
            map.get(cur).neighbors.add(map.get(nb));     // wire the copies
        }
    }
    return map.get(node);
}

• Time O(V + E) · Space O(V)

Counter-questions on this approach

⭐ "Same complexity. Why would you choose it?"

No recursion, so no stack depth limit. On a graph with 10^5 nodes the DFS would overflow and this wouldn't.

It also separates the two concerns visibly: creating a copy happens on first sighting, wiring happens when processing a node. In the DFS both are entangled in the recursion, which is more elegant but less explicit.

"Why is the root put in the map before the loop?"

So the loop's map.get(cur) always finds a copy. The invariant is "every node in the queue already has a copy in the map" — seeding the root establishes it, and the if (!map.containsKey(nb)) block maintains it.

Without the seed, the first map.get(cur) returns null and the wiring throws.

"Could a neighbour be wired twice?"

Yes, and correctly so: in an undirected graph, edge 1—2 is wired once when processing 1 and once when processing 2, giving 1'.neighbors = [2'] and 2'.neighbors = [1']. That's the intended symmetry, not duplication.

A node is only created once — guarded by the containsKey — while edges are wired once per direction.

Comparison

4. Why the Optimal Wins

The untracked version doesn't terminate, so this isn't a performance comparison — it's a correctness one.

The map solves two problems with one structure: its keys are the visited set, preventing infinite recursion, and its values are the copies, resolving forward references. Recognising that those are the same structure is the insight.

DFS and BFS are equivalent here; BFS avoids the stack and makes the create/wire split explicit.

The framing worth keeping:

Register the copy in the map BEFORE recursing into neighbours. The map's keys break the cycle; its values wire the edges — and the copy's contents can be empty when it's registered, because what's stored is the reference.

5. Java Prerequisites

The map as visited-set and copy-table

if (map.containsKey(node)) return map.get(node);   // visited check
Node copy = new Node(node.val);
map.put(node, copy);                                // register BEFORE recursing

Identity keys. Node must not override equals/hashCode, so HashMap keys on identity. Use IdentityHashMap if a class overrides them but you need identity semantics anyway.

HashMap.get(null) returns null rather than throwing — convenient, though here the null check comes first.

ArrayDeque for BFS — forbids nulls, which is fine since nodes are never null inside the loop.

6. Interview Communication Guide

Clarifying questions: Is the graph connected (yes — so one traversal reaches everything)? Directed or undirected (undirected)? Can it be empty (yes — null input)? Are values unique (yes, but I'd key on identity anyway)? Self-loops or multi-edges (no)?

The pitch

"The tree approach — recursively copy and wire the children — fails immediately here, because an undirected graph has a cycle in every edge. Node 1 lists 2, and 2 lists 1, so copying 1 copies 2 which copies 1, forever.

There are really two problems. I need to know whether I've already started copying a node, to stop the recursion. And I need to know what the copy of a node is, because when wiring node 1's neighbours, the copy of node 2 might not exist yet.

A single Map<Node, Node> from original to copy answers both: the key set is the visited set, and the values are the copies.

The critical detail is that I put the copy in the map before recursing into its neighbours. If the put came after, the recursion would reach back to the original node, find it absent, and start over — infinite.

Its neighbour list is empty at that moment, which is fine: what's stored is the object reference, and the recursion fills it in. Publishing an identity before its contents are ready is exactly how you build a cyclic structure.

O(V + E) time — each node created once, each directed edge traversed once — and O(V) space.

I'd key the map on node identity rather than on val. Values happen to be unique here, so keying on val would work, but it breaks silently the moment they aren't.

At 100 nodes the recursion is safe. For a much larger graph I'd use BFS with a queue instead."

Edge cases to volunteer:

Name the two-node case. It's the minimal input that fails without the map, and it fails as an infinite loop rather than a wrong answer — so it's unmissable once tested.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the graph were disconnected?"

One traversal from a single node reaches only its component. You'd need the full node list and a loop starting a traversal from each unvisited node — the same shape as counting islands. The problem's connectedness guarantee is what lets a single entry point suffice.

⭐ "Clone a directed graph instead."

No change at all. The algorithm never assumes symmetry — it just copies whatever neighbour lists exist. Worth noting, because "undirected" sounds like it might matter and doesn't.

"What if nodes carried mutable payloads?"

new Node(node.val) shallow-copies the value. If the payload were an object shared between original and copy, mutating it would affect both — so it wouldn't be a true deep copy. You'd need to clone the payload too, recursively.

"Serialize the graph instead of cloning it."

Assign each node an id, emit (id, val, neighbourIds) triples, and reconstruct by wiring ids in a second pass. That's what any real object serializer does — and it's why they all maintain an identity map, for exactly the reason this problem needs one.

"What if the graph had 10^6 nodes?"

DFS would overflow, so BFS with an explicit queue. The HashMap also becomes significant — a million entries with boxed keys. If node ids were dense integers, an array indexed by id would be far leaner than a hash map.

"Compare two graphs for isomorphism instead of cloning."

Much harder — graph isomorphism has no known polynomial algorithm in general. Cloning is easy because the correspondence is given by the traversal; isomorphism requires finding a correspondence. Worth naming the gap rather than treating it as a variation.