Loading…

mediumGraphsLC #133Frequently asked

Clone Graph

Q: How do you solve Clone Graph using the DFS with Original→Clone Map approach?

When to use it: The cleanest answer. Phrase it as 'recursively clone, memoizing each node's copy so cycles terminate and neighbours link to the right clones'. Clone the graph with a recursion that remembers what it has already copied. **The map is the whole trick.** `clones` maps each *original* node to its *new* clone. It does double duty: (1) it's the visited guard that prevents infinite recursion on cycles, and (2) it's the lookup that lets a freshly cloned node attach the *correct* clone instances as its neighbours rather than duplicating them. **Register before you recurse.** The ordering that makes cycles terminate: when you first see a node, create its clone and *immediately* store it in the map, *then* recurse into neighbours. If you recursed first, a cycle (A's neighbour is B, B's neighbour is A) would re-enter A before A's clone exists, and you'd recurse forever. With A registered first, the recursive call from B finds A already in the map and returns the existing clone. **Clone node, then wire edges.** For each neighbour, recursively obtain its clone (creating it if new, fetching it if seen) and append that clone to the current clone's neighbour list. Because every node is registered before its edges are processed, all neighbour clones are guaranteed to exist when referenced. **Empty input.** A null/None reference means an empty graph — return it directly before touching the map. Time complexity: O(V + E). Space complexity: O(V).

Q: How do you solve Clone Graph using the BFS with Queue and Clone Map approach?

When to use it: Offer for very large/deep graphs to avoid recursion-stack limits. Same map, iterative frontier. Same map-driven cloning, but the traversal uses an explicit queue instead of recursion. **Seed first.** Clone the starting node and store `original → clone` in the map, then enqueue the *original* start node. The map is pre-populated so we never re-clone the seed. **Process the frontier.** Dequeue an original node `u`. For each neighbour `v` of `u`: if `v` isn't in the map yet, create its clone, register it, and enqueue `v` so we'll process *its* neighbours later. Regardless, append `clones[v]` to `clones[u].neighbors` to wire the edge. Cloning-on-first-sight plus the map guarantees each node is created once and each original enters the queue once. **Why BFS over DFS.** Functionally identical; the win is avoiding deep recursion. With up to 100 nodes here it rarely matters, but it's the safe pattern for very large graphs and a good thing to mention. **Wiring is symmetric.** Because the graph is undirected, edge (u, v) appears in both u's and v's neighbour lists; processing each original exactly once and reading its full neighbour list reconstructs both directions correctly. Time complexity: O(V + E). Space complexity: O(V).

LCPractice

Graphs · 3 of 34 · 9 min

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors:

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

The graph is given via the reference to the first node. Test cases use an adjacency-list representation; node.val equals the node's 1-indexed position.

In plain English

Produce an entirely new graph that mirrors the original: same values, same adjacency structure, but composed of brand-new Node objects so the copy shares nothing with the input. The graph is undirected and may contain cycles, so we must avoid revisiting nodes endlessly.

Examples

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Note: A 4-cycle: 1-2-3-4-1. The clone has identical structure with new node objects.

Example 2

Input: adjList = [[]]
Output: [[]]
Note: A single node with no neighbours; clone it alone.

Example 3

Input: adjList = []
Output: []
Note: Empty graph (null input) → return null.

Constraints

The number of nodes is in the range [0, 100]
1 ≤ Node.val ≤ 100 and Node.val is unique
There are no repeated edges and no self-loops
The graph is connected and all nodes can be reached from the given node

Clarifying questions4First question: Can the input be null / an empty graph?Explore questions

Q1.Can the input be null / an empty graph?
Yes — node count can be 0. I return null/None immediately for an empty input.
Q2.Is it guaranteed connected, or could there be isolated components?
The prompt says connected and fully reachable from the given node, so one traversal covers everything. If it weren't, I'd loop over all nodes.
Q3.Are there cycles or self-loops?
Cycles yes (undirected edges form them), self-loops no per constraints. The original→clone map is what stops cycles from looping forever.
Q4.Must the copy be fully independent of the original?
Yes — a deep copy. Mutating the clone must never affect the input, so every node and neighbour reference is freshly created.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Do a graph traversal (DFS or BFS) while maintaining a hash map from each original node to its freshly created copy. The map serves two roles: it prevents infinite loops on cycles, and it lets you wire copied neighbours to the correct clone instances. Each node and edge is visited once → O(V + E) time and space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle cycles in a deep copy by memoizing original→clone, and whether you register the clone before recursing so the traversal terminates.

Where candidates slip

Creating a clone before checking the map (duplicating nodes), recursing before registering the clone (infinite loop on cycles), or sharing the original neighbour objects instead of their clones.

How to stand out

Name the map's dual purpose (cycle guard + reference resolver), give both DFS and BFS, register-before-recurse explicitly, and discuss the null/empty edge case and why it's a true deep copy.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	DFS with Original→Clone Map	`O(V + E)`	`O(V)`	The cleanest answer. Phrase it as 'recursively clone, memoizing each node's copy so cycles terminate and neighbours link to the right clones'.	Read
2	BFS with Queue and Clone MapOptimal	`O(V + E)`	`O(V)`	Offer for very large/deep graphs to avoid recursion-stack limits. Same map, iterative frontier.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewDeep copy a graph with cyclesEmpty / null input?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

DFS with Original→Clone Map

TimeO(V + E)SpaceO(V)

The cleanest answer. Phrase it as 'recursively clone, memoizing each node's copy so cycles terminate and neighbours link to the right clones'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you naively recurse into neighbours of an undirected graph, what stops you looping 1→2→1→2 forever?

2Hint 2Explore hint

Keep a map from each original node to its clone. Before exploring a node's neighbours, put its clone in the map.

3Hint 3Explore hint

When you reach a node already in the map, return its existing clone instead of making a new one — that both stops cycles and ensures neighbours point to shared clones.

A · Core idea

Clone the graph with a recursion that remembers what it has already copied.

The map is the whole trick. clones maps each original node to its new clone. It does double duty: (1) it's the visited guard that prevents infinite recursion on cycles, and (2) it's the lookup that lets a freshly cloned node attach the correct clone instances as its neighbours rather than duplicating them.

Register before you recurse. The ordering that makes cycles terminate: when you first see a node, create its clone and immediately store it in the map, then recurse into neighbours. If you recursed first, a cycle (A's neighbour is B, B's neighbour is A) would re-enter A before A's clone exists, and you'd recurse forever. With A registered first, the recursive call from B finds A already in the map and returns the existing clone.

Clone node, then wire edges. For each neighbour, recursively obtain its clone (creating it if new, fetching it if seen) and append that clone to the current clone's neighbour list. Because every node is registered before its edges are processed, all neighbour clones are guaranteed to exist when referenced.

Empty input. A null/None reference means an empty graph — return it directly before touching the map.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

adjList = [[2,4],[1,3],[2,4],[1,3]] (4-cycle 1-2-3-4-1)

Hash-map state

clone 1

ValueIndex / state

1→ copy1

Continue scanning

Final resultdeep copy of the 4-cycle

C · Code with teaching comments

Reference implementation previewpublic Node cloneGraph(Node node) { if (node == null) return null; Map<Node, Node> clones = new HashMap<>(); return dfs(node, clones); }Explore the full code

solution.javaJava

DFS with Original→Clone Map — reference

4 teaching notes

1
public Node cloneGraph(Node node) {
2
    // Empty graph guard — nothing to clone.
3
    if (node == null) return null;
4
    Map<Node, Node> clones = new HashMap<>();
5
    return dfs(node, clones);
6
}
7
 
8
private Node dfs(Node node, Map<Node, Node> clones) {
9
    if (clones.containsKey(node)) {
10
        return clones.get(node);
11
    }
12
    Node copy = new Node(node.val);
13
    // Crucial ordering: register the clone first so a cycle finds it instead of
14
    // recursing forever.
15
    clones.put(node, copy); // register BEFORE recursing
16
    for (Node nb : node.neighbors) {
17
        // Wire the clone's neighbour to the neighbour's clone (created or fetched).
18
        copy.neighbors.add(dfs(nb, clones));
19
    }
20
    return copy;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(V + E) timeO(V) spaceOpen the invariant and proofExplore the proof

Think of the map as a 'translation table' from old-world nodes to new-world nodes. Cloning is just walking the old graph and, for every node and edge, writing down its translation once. Revisits are free lookups, which is exactly why cycles cost nothing.

ComplexityO(V + E) time, O(V) space — Each node is cloned exactly once (guarded by the map) and each undirected edge is traversed twice (once from each endpoint) → O(V + E). The map holds V entries and recursion depth is O(V) → O(V) space.

E · Edge cases and pitfalls6null input — Return null immediately — empty graph.Explore edge cases

Edge cases handled

null inputReturn null immediately — empty graph.
single node [[]]Clone one node with empty neighbours; no recursion into others.
two-node cycle 1-2Register 1, recurse to 2, 2's neighbour 1 found in map → links to copy1; terminates.

Pitfalls

Recursing into neighbours BEFORE registering the clone — infinite recursion on any cycle.
Creating a new clone without checking the map first — duplicate nodes and broken aliasing.
Appending the original neighbour instead of its clone — the copy ends up referencing the input graph.

03.2

Approach 2 of 2 · Optimal

BFS with Queue and Clone Map

TimeO(V + E)SpaceO(V)

Offer for very large/deep graphs to avoid recursion-stack limits. Same map, iterative frontier.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Clone the start node first and put (original → clone) in the map. Then process the graph level by level with a queue.

2Hint 2Explore hint

Dequeue an original node; for each of its neighbours, clone it if unseen (register + enqueue), then link the current clone to that neighbour's clone.

3Hint 3Explore hint

Clone nodes when you first see them (at enqueue), and only enqueue each original once — the map enforces that.

A · Core idea

Same map-driven cloning, but the traversal uses an explicit queue instead of recursion.

Seed first. Clone the starting node and store original → clone in the map, then enqueue the original start node. The map is pre-populated so we never re-clone the seed.

Process the frontier. Dequeue an original node u. For each neighbour v of u: if v isn't in the map yet, create its clone, register it, and enqueue v so we'll process its neighbours later. Regardless, append clones[v] to clones[u].neighbors to wire the edge. Cloning-on-first-sight plus the map guarantees each node is created once and each original enters the queue once.

Why BFS over DFS. Functionally identical; the win is avoiding deep recursion. With up to 100 nodes here it rarely matters, but it's the safe pattern for very large graphs and a good thing to mention.

Wiring is symmetric. Because the graph is undirected, edge (u, v) appears in both u's and v's neighbour lists; processing each original exactly once and reading its full neighbour list reconstructs both directions correctly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

adjList = [[2],[1,3],[2]] (path 1-2-3)

Interactive diagram

Cloned graph mirrors the original

seed

Active call / nodeSupporting contextReturned stateNot active

New node objects, identical adjacency; nothing shared with the input.

Final resultdeep copy of the path

C · Code with teaching comments

solution.javaJava

BFS with Queue and Clone Map — optimal

3 teaching notes

1
public Node cloneGraph(Node node) {
2
    if (node == null) return null;
3
    Map<Node, Node> clones = new HashMap<>();
4
    // Pre-clone the seed so it's never duplicated when revisited.
5
    clones.put(node, new Node(node.val));
6
    Queue<Node> q = new LinkedList<>();
7
    q.offer(node);
8
    while (!q.isEmpty()) {
9
        Node u = q.poll();
10
        for (Node nb : u.neighbors) {
11
            if (!clones.containsKey(nb)) {
12
                clones.put(nb, new Node(nb.val));
13
                q.offer(nb);
14
            }
15
            // Wire the edge between clones; runs for every neighbour, seen or new.
16
            clones.get(u).neighbors.add(clones.get(nb));
17
        }
18
    }
19
    return clones.get(node);
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(V + E) timeO(V) spaceOpen the invariant and proofExplore the proof

DFS and BFS differ only in the order nodes are discovered; the cloning contract — 'create each node's copy once, then translate every edge through the map' — is identical. Choosing BFS is purely about trading the call stack for a heap-allocated queue.

ComplexityO(V + E) time, O(V) space — Each node enters the queue once (O(V)); each edge is examined once per endpoint (O(E)). The map and queue hold O(V) entries. Total O(V + E) time, O(V) space.

E · Edge cases and pitfalls6null input — Return null before seeding the map.Explore edge cases

Edge cases handled

null inputReturn null before seeding the map.
self-referential-free cycleMap prevents re-enqueueing; each node processed once even in a cycle.
dense graphEach edge linked once per endpoint; O(V+E) holds.

Pitfalls

Forgetting to pre-clone/seed the start node — it gets re-created or linked incorrectly.
Enqueueing a neighbour every time it's seen instead of only on first sight — re-processing and duplicate edges.
Wiring edges with original nodes rather than clones — copy leaks references to the input.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic Node cloneGraph(Node node) { if (node == null) return null; Map<Node, Node> clones = new HashMap<>(); clones.put(node, new Node(node.val)); Queue<Node> q = new LinkedList<>();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Recurse-before-register (infinite loop)

If you recurse into neighbours before putting the current clone in the map, a cycle re-enters the same node before its clone exists, recursing forever.

Explore the code comparison

Don't write this

def dfs(curr):
    copy = Node(curr.val)
    for nb in curr.neighbors:
        copy.neighbors.append(dfs(nb))  # cycle → infinite recursion
    clones[curr] = copy
    return copy

Write this instead

def dfs(curr):
    if curr in clones:
        return clones[curr]
    copy = Node(curr.val)
    clones[curr] = copy            # register FIRST
    for nb in curr.neighbors:
        copy.neighbors.append(dfs(nb))
    return copy

Linking original neighbours instead of clones

Appending the input's neighbour objects makes the 'copy' point back into the original graph, so it isn't a deep copy and mutations leak across.

Explore the code comparison

Don't write this

for (Node nb : u.neighbors) {
    clones.get(u).neighbors.add(nb); // original, not its clone
}

Write this instead

for (Node nb : u.neighbors) {
    clones.get(u).neighbors.add(clones.get(nb)); // the clone
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Traversal (DFS/BFS) + hash map old node → cloned node

Code pattern to memorize

clones = {}
def dfs(node):
    if node in clones: return clones[node]
    copy = Node(node.val)
    clones[node] = copy            # register BEFORE recursing
    for nb in node.neighbors:
        copy.neighbors.append(dfs(nb))
    return copy

Rules to remember

1Register the clone in the map before recursing into neighbours — otherwise cycles cause infinite recursion.
2The map keys are original nodes; values are their cloned counterparts.
3Create a node's clone exactly once; subsequent visits return the existing clone from the map.
4Clone the node first, then its edges — wiring neighbours requires their clones to exist (the map guarantees they will).
5Handle the empty input (null/None) up front — return it directly.

Use this pattern when

Deep-copying a graph / linked structure with shared references or cycles
Any 'duplicate this structure exactly' where nodes may be revisited
Mapping originals to copies to preserve identity/aliasing
Traversal where you must avoid reprocessing already-seen nodes

Choose another pattern when

Tree (no cycles, no shared children) → a plain recursion without the map works
You only need to traverse/measure, not copy → a visited set suffices, no clone map
Immutable nodes that can be shared → no deep copy needed at all

Interview takeaway

Clone Graph is the canonical 'old → new' hash-map traversal: the map both deduplicates visits and resolves neighbour references to the right clones. The exact same map-of-copies trick powers Copy List with Random Pointer and any deep-copy-with-cycles problem.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternDeep copy via traversal + original→clone hash map. The map both prevents cycle re-visits and resolves neighbour references. Same family as Copy List with Random Pointer and Clone Binary Tree With Random Pointer.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Copy List with Random Pointer
Coming soon
Same original→clone map to resolve arbitrary 'random' pointers during a deep copy.
Clone Binary Tree With Random Pointer
Coming soon
Tree variant of the map-of-copies technique with an extra random link.
Number of Islands
Grid-as-graph traversal sibling — same DFS/BFS skeleton, different goal.
Reconstruct Itinerary
Coming soon
Graph traversal building structure as you go — Hierholzer's Eulerian path.

Same pattern

←

Course Schedule (Topological Sort)

Continue · Next problem

Pacific Atlantic Water Flow

mediumGraphsLC #133Frequently asked

Clone Graph

LCPractice

Graphs · 3 of 34 · 9 min

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors:

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

The graph is given via the reference to the first node. Test cases use an adjacency-list representation; node.val equals the node's 1-indexed position.

In plain English

Examples

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Note: A 4-cycle: 1-2-3-4-1. The clone has identical structure with new node objects.

Example 2

Input: adjList = [[]]
Output: [[]]
Note: A single node with no neighbours; clone it alone.

Example 3

Input: adjList = []
Output: []
Note: Empty graph (null input) → return null.

Constraints

The number of nodes is in the range [0, 100]
1 ≤ Node.val ≤ 100 and Node.val is unique
There are no repeated edges and no self-loops
The graph is connected and all nodes can be reached from the given node

Clarifying questions4First question: Can the input be null / an empty graph?Explore questions

Q1.Can the input be null / an empty graph?
Yes — node count can be 0. I return null/None immediately for an empty input.
Q2.Is it guaranteed connected, or could there be isolated components?
The prompt says connected and fully reachable from the given node, so one traversal covers everything. If it weren't, I'd loop over all nodes.
Q3.Are there cycles or self-loops?
Cycles yes (undirected edges form them), self-loops no per constraints. The original→clone map is what stops cycles from looping forever.
Q4.Must the copy be fully independent of the original?
Yes — a deep copy. Mutating the clone must never affect the input, so every node and neighbour reference is freshly created.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle cycles in a deep copy by memoizing original→clone, and whether you register the clone before recursing so the traversal terminates.

Where candidates slip

Creating a clone before checking the map (duplicating nodes), recursing before registering the clone (infinite loop on cycles), or sharing the original neighbour objects instead of their clones.

How to stand out

Name the map's dual purpose (cycle guard + reference resolver), give both DFS and BFS, register-before-recurse explicitly, and discuss the null/empty edge case and why it's a true deep copy.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	DFS with Original→Clone Map	`O(V + E)`	`O(V)`	The cleanest answer. Phrase it as 'recursively clone, memoizing each node's copy so cycles terminate and neighbours link to the right clones'.	Read
2	BFS with Queue and Clone MapOptimal	`O(V + E)`	`O(V)`	Offer for very large/deep graphs to avoid recursion-stack limits. Same map, iterative frontier.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

DFS with Original→Clone Map

TimeO(V + E)SpaceO(V)

The cleanest answer. Phrase it as 'recursively clone, memoizing each node's copy so cycles terminate and neighbours link to the right clones'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you naively recurse into neighbours of an undirected graph, what stops you looping 1→2→1→2 forever?

2Hint 2Explore hint

Keep a map from each original node to its clone. Before exploring a node's neighbours, put its clone in the map.

3Hint 3Explore hint

When you reach a node already in the map, return its existing clone instead of making a new one — that both stops cycles and ensures neighbours point to shared clones.

A · Core idea

Clone the graph with a recursion that remembers what it has already copied.

Empty input. A null/None reference means an empty graph — return it directly before touching the map.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

adjList = [[2,4],[1,3],[2,4],[1,3]] (4-cycle 1-2-3-4-1)

Hash-map state

clone 1

ValueIndex / state

1→ copy1

Continue scanning

Final resultdeep copy of the 4-cycle

C · Code with teaching comments

Reference implementation previewpublic Node cloneGraph(Node node) { if (node == null) return null; Map<Node, Node> clones = new HashMap<>(); return dfs(node, clones); }Explore the full code

solution.javaJava

DFS with Original→Clone Map — reference

4 teaching notes

1
public Node cloneGraph(Node node) {
2
    // Empty graph guard — nothing to clone.
3
    if (node == null) return null;
4
    Map<Node, Node> clones = new HashMap<>();
5
    return dfs(node, clones);
6
}
7
 
8
private Node dfs(Node node, Map<Node, Node> clones) {
9
    if (clones.containsKey(node)) {
10
        return clones.get(node);
11
    }
12
    Node copy = new Node(node.val);
13
    // Crucial ordering: register the clone first so a cycle finds it instead of
14
    // recursing forever.
15
    clones.put(node, copy); // register BEFORE recursing
16
    for (Node nb : node.neighbors) {
17
        // Wire the clone's neighbour to the neighbour's clone (created or fetched).
18
        copy.neighbors.add(dfs(nb, clones));
19
    }
20
    return copy;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(V + E) timeO(V) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6null input — Return null immediately — empty graph.Explore edge cases

Edge cases handled

null inputReturn null immediately — empty graph.
single node [[]]Clone one node with empty neighbours; no recursion into others.
two-node cycle 1-2Register 1, recurse to 2, 2's neighbour 1 found in map → links to copy1; terminates.

Pitfalls

Recursing into neighbours BEFORE registering the clone — infinite recursion on any cycle.
Creating a new clone without checking the map first — duplicate nodes and broken aliasing.
Appending the original neighbour instead of its clone — the copy ends up referencing the input graph.

03.2

Approach 2 of 2 · Optimal

BFS with Queue and Clone Map

TimeO(V + E)SpaceO(V)

Offer for very large/deep graphs to avoid recursion-stack limits. Same map, iterative frontier.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Clone the start node first and put (original → clone) in the map. Then process the graph level by level with a queue.

2Hint 2Explore hint

Dequeue an original node; for each of its neighbours, clone it if unseen (register + enqueue), then link the current clone to that neighbour's clone.

3Hint 3Explore hint

Clone nodes when you first see them (at enqueue), and only enqueue each original once — the map enforces that.

A · Core idea

Same map-driven cloning, but the traversal uses an explicit queue instead of recursion.

Seed first. Clone the starting node and store original → clone in the map, then enqueue the original start node. The map is pre-populated so we never re-clone the seed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

adjList = [[2],[1,3],[2]] (path 1-2-3)

Interactive diagram

Cloned graph mirrors the original

seed

Active call / nodeSupporting contextReturned stateNot active

New node objects, identical adjacency; nothing shared with the input.

Final resultdeep copy of the path

C · Code with teaching comments

solution.javaJava

BFS with Queue and Clone Map — optimal

3 teaching notes

1
public Node cloneGraph(Node node) {
2
    if (node == null) return null;
3
    Map<Node, Node> clones = new HashMap<>();
4
    // Pre-clone the seed so it's never duplicated when revisited.
5
    clones.put(node, new Node(node.val));
6
    Queue<Node> q = new LinkedList<>();
7
    q.offer(node);
8
    while (!q.isEmpty()) {
9
        Node u = q.poll();
10
        for (Node nb : u.neighbors) {
11
            if (!clones.containsKey(nb)) {
12
                clones.put(nb, new Node(nb.val));
13
                q.offer(nb);
14
            }
15
            // Wire the edge between clones; runs for every neighbour, seen or new.
16
            clones.get(u).neighbors.add(clones.get(nb));
17
        }
18
    }
19
    return clones.get(node);
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(V + E) timeO(V) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6null input — Return null before seeding the map.Explore edge cases

Edge cases handled

null inputReturn null before seeding the map.
self-referential-free cycleMap prevents re-enqueueing; each node processed once even in a cycle.
dense graphEach edge linked once per endpoint; O(V+E) holds.

Pitfalls

Forgetting to pre-clone/seed the start node — it gets re-created or linked incorrectly.
Enqueueing a neighbour every time it's seen instead of only on first sight — re-processing and duplicate edges.
Wiring edges with original nodes rather than clones — copy leaks references to the input.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Recurse-before-register (infinite loop)

If you recurse into neighbours before putting the current clone in the map, a cycle re-enters the same node before its clone exists, recursing forever.

Explore the code comparison

Don't write this

def dfs(curr):
    copy = Node(curr.val)
    for nb in curr.neighbors:
        copy.neighbors.append(dfs(nb))  # cycle → infinite recursion
    clones[curr] = copy
    return copy

Write this instead

def dfs(curr):
    if curr in clones:
        return clones[curr]
    copy = Node(curr.val)
    clones[curr] = copy            # register FIRST
    for nb in curr.neighbors:
        copy.neighbors.append(dfs(nb))
    return copy

Linking original neighbours instead of clones

Appending the input's neighbour objects makes the 'copy' point back into the original graph, so it isn't a deep copy and mutations leak across.

Explore the code comparison

Don't write this

for (Node nb : u.neighbors) {
    clones.get(u).neighbors.add(nb); // original, not its clone
}

Write this instead

for (Node nb : u.neighbors) {
    clones.get(u).neighbors.add(clones.get(nb)); // the clone
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Traversal (DFS/BFS) + hash map old node → cloned node

Code pattern to memorize

clones = {}
def dfs(node):
    if node in clones: return clones[node]
    copy = Node(node.val)
    clones[node] = copy            # register BEFORE recursing
    for nb in node.neighbors:
        copy.neighbors.append(dfs(nb))
    return copy

Rules to remember

1Register the clone in the map before recursing into neighbours — otherwise cycles cause infinite recursion.
2The map keys are original nodes; values are their cloned counterparts.
3Create a node's clone exactly once; subsequent visits return the existing clone from the map.
4Clone the node first, then its edges — wiring neighbours requires their clones to exist (the map guarantees they will).
5Handle the empty input (null/None) up front — return it directly.

Use this pattern when

Deep-copying a graph / linked structure with shared references or cycles
Any 'duplicate this structure exactly' where nodes may be revisited
Mapping originals to copies to preserve identity/aliasing
Traversal where you must avoid reprocessing already-seen nodes

Choose another pattern when

Tree (no cycles, no shared children) → a plain recursion without the map works
You only need to traverse/measure, not copy → a visited set suffices, no clone map
Immutable nodes that can be shared → no deep copy needed at all

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Copy List with Random Pointer
Coming soon
Same original→clone map to resolve arbitrary 'random' pointers during a deep copy.
Clone Binary Tree With Random Pointer
Coming soon
Tree variant of the map-of-copies technique with an extra random link.
Number of Islands
Grid-as-graph traversal sibling — same DFS/BFS skeleton, different goal.
Reconstruct Itinerary
Coming soon
Graph traversal building structure as you go — Hierholzer's Eulerian path.

Same pattern

←

Course Schedule (Topological Sort)

Continue · Next problem

Pacific Atlantic Water Flow