Frontend Beauty
ESC

Type to search the knowledge base.

Clone Graph

Deep-copy an undirected connected graph — BFS/DFS with a map from original node to clone, neighbor wiring pitfalls.

intermediate3 min read
  • dsa
  • graph
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

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

// 1 -- 2
// |    |
// 4 -- 3
// clone must have new node objects, same connectivity

Cycles exist. A naïve recursive clone without a map infinite-loops.

Brute idea that fails

JSON serialize — nodes aren’t trees; cycles break it. Copying only the start node’s neighbor array by reference shares structure. You need a visited map: old → new.

Optimal: DFS or BFS with clone map

DFS

class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const map = new Map<Node, Node>();

  function dfs(n: Node): Node {
    if (map.has(n)) return map.get(n)!;
    const copy = new Node(n.val);
    map.set(n, copy); // set before recursing — breaks cycles
    for (const nei of n.neighbors) {
      copy.neighbors.push(dfs(nei));
    }
    return copy;
  }

  return dfs(node);
}

BFS

function cloneGraphBfs(node: Node | null): Node | null {
  if (!node) return null;
  const map = new Map<Node, Node>();
  map.set(node, new Node(node.val));
  const q: Node[] = [node];
  let head = 0;

  while (head < q.length) {
    const cur = q[head++];
    const curCopy = map.get(cur)!;
    for (const nei of cur.neighbors) {
      if (!map.has(nei)) {
        map.set(nei, new Node(nei.val));
        q.push(nei);
      }
      curCopy.neighbors.push(map.get(nei)!);
    }
  }
  return map.get(node)!;
}
Time O(V + E)
Space O(V) for map + queue/stack

Walk a 2-node cycle

1 ⇄ 2

  1. Clone 1, map{1→1’}.
  2. Neighbor 2 not cloned → clone 2, map{2→2’}.
  3. 2’s neighbor 1 already in map → push 1’, not re-enter.
  4. 1’s neighbors get 2’. Done.

Edge cases

  • null input → null
  • Single node with empty neighbors
  • Single node with self-loop (rare in LC; handle via map)
  • Dense graph — O(V+E) still

Common mistakes

  • Mapping by val only (vals can theoretically collide in variants; use node identity)
  • Creating the clone after recursing (cycle → stack overflow)
  • Shallow copy of neighbors array

Interview delivery

  1. Deep copy + cycles ⇒ hash map.
  2. Register clone before exploring neighbors.
  3. Implement DFS or BFS fully.
  4. Null and single-node cases.
  5. O(V+E).

Mental model

Cloning a graph is “map identity while traversing.” The map serves two jobs: (1) return the already-built clone when you re-encounter a node, (2) break infinite recursion on cycles. You must map.set(original, copy) before walking neighbors — same discipline as copying structures with back-edges.

Frontend analogy: cloning a component tree with circular refs (parent pointers) or duplicating a scene graph in a canvas editor.

BFS vs DFS — pick one and finish

DFS is shorter. BFS is safer on deep graphs if recursion limits worry you (JS engines ~thousands of frames). Either is O(V+E). Don’t mix half-BFS half-DFS mid coding.

Out-loud answer

“Deep copy of undirected connected graph. HashMap old→new. Create clone, register in map, then wire neighbors recursively or with a queue. Null input returns null. Time and space linear in vertices plus edges.”

Further reading