Clone Graph
Understand the problem
Given a node in a connected undirected graph.
- Each node holds a value
val(an integer) and a list of neighborsneighbors. - Create a deep copy of the whole graph.
ts
class Node {
val: number
neighbors: Node[]
constructor(val: number, neighbors: Node[] = []) {
this.val = val
this.neighbors = neighbors
}
}
// Graph: 1 -- 2
// | |
// 4 -- 3
// Input: node = Node(1)
// Output: a copy Node(1') with 1'→2'→3'→4'→1' (identical structure, different objects)The challenge: the graph can contain cycles — you need a Hash Map to avoid copying forever.
Basic approach
Does not terminate on a graph with a cyclets
// Manual BFS without a Hash Map — loops forever on cycles
// This is the WRONG approach, shown to illustrate the problem:
function cloneGraphNaive(node: Node | null): Node | null {
if (!node) return null
const newNode = new Node(node.val)
// Copying neighbors directly re-clones nodes already cloned → infinite recursion
for (const neighbor of node.neighbors) {
newNode.neighbors.push(cloneGraphNaive(neighbor)!) // ❌ infinite loop!
}
return newNode
}Why this approach is slow:
There's no mechanism for tracking nodes that have already been copied.
A Hash Map (old → new) is the key to breaking cycles.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.