Marauder Bot

Problem

You are given a reference to a node inside a connected, undirected graph, where each node holds a value and a list of neighbor references. Produce a complete deep copy of the graph (new node objects with the same values and connectivity) and return a reference to the cloned version of the starting node.

Example. A graph where node 1 connects to nodes 2 and 4 must be copied into an entirely separate set of node objects that still show 1 connected to the clones of 2 and 4.

Key idea

A naive copy that walks neighbors recursively runs into two problems: cycles make naive recursion never terminate, and a node reachable through multiple paths would otherwise get cloned more than once, breaking the shared structure. Both are solved by one hash map from original node to its clone. Traverse the graph with depth-first or breadth-first search starting from the given node. The first time a node is encountered, immediately create its clone and record the mapping before visiting any neighbors: that early registration is what lets a later path back to the same node find the existing clone instead of recursing again. Then, for each neighbor of the original node, look up or create its clone and attach it to the current clone's neighbor list, wiring the copy to match the original's connectivity.

Solution

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 === null) {
    return null;
  }

  const cloned = new Map<Node, Node>(); // original node to its clone, also breaks cycles

  function dfs(original: Node): Node {
    const existing = cloned.get(original);
    if (existing !== undefined) {
      return existing; // already cloned: reuse it instead of recursing again
    }

    const clone = new Node(original.val);
    cloned.set(original, clone); // register before recursing into neighbors so cycles terminate

    for (const neighbor of original.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }

    return clone;
  }

  return dfs(node);
}

Complexity

Time: O(V + E). Every node is cloned once and every edge is examined once to wire up neighbor lists.
Space: O(V). The map from original to cloned nodes, plus recursion or queue overhead.

Watch out for

Register a node's clone in the map before recursing into its neighbors, or cycles cause infinite recursion.
Give each cloned node its own new neighbor list rather than reusing the original's list object.
Handle the single-node-with-no-neighbors case, and the empty-graph case where the input node is null.

Pattern

This is a graph traversal paired with a visited map used both to prevent revisiting and to preserve node identity across the copy. The same clone-plus-map technique solves Copy List with Random Pointer.

Clone Graph