#44 · Graphs

Clone Graph

Given a reference to a node in a connected undirected graph, return a deep copy: new nodes with the same values and the same neighbour structure, sharing nothing with the original.

MediumLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Original → clone map

A table from each original node to its clone. It answers "have I already copied this node?" in O(1), which is what keeps cycles from looping forever, and it lets you attach the right clone when linking neighbours.

Memory layout

A hash table keyed by node identity (or an array indexed by value when values are small and unique). One entry per node.

Operation	Cost
lookup / insert	O(1) average
whole copy	O(V + E) time, O(V) extra space

Traversal frontier (stack, queue or call stack)

Which original nodes still need their neighbours linked. A stack gives depth-first order, a queue gives breadth-first order, and recursion uses the call stack as the stack.

Memory layout

A dynamic array used from one end (stack) or both ends (queue); recursion depth is up to V for a path-like graph.

Operation	Cost
push / pop	O(1)

Why it fits

A graph can contain cycles. Without a table of already-copied nodes, a traversal would copy the same node forever, and even without cycles the same node would be copied once per path leading to it.
The table also solves the wiring problem: when node A lists B as a neighbour, you need A's clone to point at B's clone, not at a fresh copy. Looking up B in the table returns exactly that.
Registering a clone before visiting its neighbours is the key ordering rule: a neighbour that points back finds the clone already in the table and the recursion ends.

Why alternatives degrade

Plain recursion without a table:: Never terminates on a cycle (every node here is in one), and on a DAG-like region it copies shared nodes many times.
Copy by serialization (stringify and parse):: Works for trees, but a cyclic graph cannot be turned into a finite text without extra identifiers, which is the table in disguise.
A set of visited nodes only:: It tells you a node was seen but not where its clone is, so you cannot connect clones to each other.

Four approaches, from naive to production

1 · beginner

Three passes: collect, create, wire

time O(V + E)space O(V)

First walk the graph to list every node. Then create one empty clone per node and store the pairs in a table. Finally, for every original node, add to its clone a link to the clone of each neighbour.

Node* cloneGraph(Node* node) {
    if (node == nullptr) return nullptr;
    vector<Node*> all;
    unordered_set<Node*> seen;
    vector<Node*> stack = {node};
    seen.insert(node);
    while (!stack.empty()) {
        Node* cur = stack.back(); stack.pop_back();
        all.push_back(cur);
        for (Node* nb : cur->neighbors) {
            if (!seen.count(nb)) {
                seen.insert(nb);
                stack.push_back(nb);
            }
        }
    }
    unordered_map<Node*, Node*> copy;
    for (Node* old : all) copy[old] = new Node(old->val);
    for (Node* old : all) {
        for (Node* nb : old->neighbors) copy[old]->neighbors.push_back(copy[nb]);
    }
    return copy[node];
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    List<Node> all = new ArrayList<>();
    Set<Node> seen = new HashSet<>();
    Deque<Node> stack = new ArrayDeque<>(); stack.push(node);
    seen.add(node);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        all.add(cur);
        for (Node nb : cur.neighbors) {
            if (!seen.contains(nb)) {
                seen.add(nb);
                stack.push(nb);
            }
        }
    }
    Map<Node, Node> copy = new HashMap<>();
    for (Node old : all) copy.put(old, new Node(old.val));
    for (Node old : all) {
        for (Node nb : old.neighbors) copy.get(old).neighbors.add(copy.get(nb));
    }
    return copy.get(node);
}

def clone_graph(node):
    if node is None: return None
    all_nodes = []
    seen = set()
    stack = [node]
    seen.add(node)
    while stack:
        cur = stack.pop()
        all_nodes.append(cur)
        for nb in cur.neighbors:
            if nb not in seen:
                seen.add(nb)
                stack.append(nb)
    copy = {}
    for old in all_nodes: copy[old] = Node(old.val)
    for old in all_nodes:
        for nb in old.neighbors: copy[old].neighbors.append(copy[nb])
    return copy[node]

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const all: GraphNode[] = [];
  const seen = new Set<GraphNode>();
  const stack: GraphNode[] = [node];
  seen.add(node);
  while (stack.length > 0) {
    const cur = stack.pop()!;
    all.push(cur);
    for (const nb of cur.neighbors) {
      if (!seen.has(nb)) {
        seen.add(nb);
        stack.push(nb);
      }
    }
  }
  const copy = new Map<GraphNode, GraphNode>();
  for (const old of all) copy.set(old, new GraphNode(old.val));
  for (const old of all) {
    for (const nb of old.neighbors) copy.get(old)!.neighbors.push(copy.get(nb)!);
  }
  return copy.get(node)!;
}

Flaws & bottlenecks

Three separate loops over the same data, plus a separate "seen" set and node list, even though one traversal could do all of it.
Memory for the extra list of all nodes.
More code, so more places for a mistake (forgetting to add a node to the list breaks the wiring pass).

Interviewer cross-questions

Why create all clones before wiring?

Say: When wiring node A to neighbour B you need B's clone to exist. Creating every clone first guarantees that, with no ordering problems.

Is the "seen" set needed in pass 1?

Say: Yes. The graph has cycles, so without it the walk would revisit nodes forever.

Can it be done in one pass?

Say: Yes: create each clone the first time its original is discovered, and link as you go. That is the BFS or DFS version.

2 · intermediate

One BFS with a copy table

time O(V + E)space O(V)

Clone the entry node, then process a queue. For each neighbour, create its clone if the table does not have one (and queue the neighbour), then attach the neighbour's clone to the current clone.

Node* cloneGraph(Node* node) {
    if (node == nullptr) return nullptr;
    unordered_map<Node*, Node*> copy; copy[node] = new Node(node->val);
    queue<Node*> q; q.push(node);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        for (Node* nb : cur->neighbors) {
            if (!copy.count(nb)) {
                copy[nb] = new Node(nb->val);
                q.push(nb);
            }
            copy[cur]->neighbors.push_back(copy[nb]);
        }
    }
    return copy[node];
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> copy = new HashMap<>(); copy.put(node, new Node(node.val));
    Queue<Node> queue = new ArrayDeque<>(); queue.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node nb : cur.neighbors) {
            if (!copy.containsKey(nb)) {
                copy.put(nb, new Node(nb.val));
                queue.add(nb);
            }
            copy.get(cur).neighbors.add(copy.get(nb));
        }
    }
    return copy.get(node);
}

def clone_graph(node):
    if node is None: return None
    copy = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for nb in cur.neighbors:
            if nb not in copy:
                copy[nb] = Node(nb.val)
                queue.append(nb)
            copy[cur].neighbors.append(copy[nb])
    return copy[node]

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const copy = new Map<GraphNode, GraphNode>([[node, new GraphNode(node.val)]]);
  const queue: GraphNode[] = [node];
  while (queue.length > 0) {
    const cur = queue.shift()!;
    for (const nb of cur.neighbors) {
      if (!copy.has(nb)) {
        copy.set(nb, new GraphNode(nb.val));
        queue.push(nb);
      }
      copy.get(cur)!.neighbors.push(copy.get(nb)!);
    }
  }
  return copy.get(node)!;
}

Flaws & bottlenecks

Removing from the front of a plain array is O(n) in some languages (use a real queue or a head index).
The queue and the table both store every node (two O(V) structures).
Each undirected edge is linked twice, once from each side (that is correct, but easy to forget when counting edges).

Interviewer cross-questions

Why does the table double as the "visited" set?

Say: A node has a clone exactly when it has been discovered. So "no clone yet" is the same as "not seen yet".

Why is each edge pushed twice?

Say: An undirected edge appears in both nodes' neighbour lists. Each side must link to the other, so both directions are wired.

What if the graph is not connected?

Say: The problem gives one entry node of a connected graph. For several components you would loop over all nodes and start a traversal from each uncopied one.

3 · advanced

Recursive DFS, memoized by the table

time O(V + E)space O(V) table + O(V) recursion

dfs(node) returns its clone. If the table has one, return it. Otherwise create the clone, register it, then fill its neighbour list with dfs of each original neighbour.

Node* cloneGraph(Node* node) {
    unordered_map<Node*, Node*> copy;
    function<Node*(Node*)> dfs = [&](Node* cur) -> Node* {
        auto existing = copy.find(cur);
        if (existing != copy.end()) return existing->second;
        Node* clone = new Node(cur->val);
        copy[cur] = clone;
        for (Node* nb : cur->neighbors) clone->neighbors.push_back(dfs(nb));
        return clone;
    };
    return node == nullptr ? nullptr : dfs(node);
}

public Node cloneGraph(Node node) {
    Map<Node, Node> copy = new HashMap<>();
    return node == null ? null : dfs(node, copy);
}
private Node dfs(Node cur, Map<Node, Node> copy) {
    Node existing = copy.get(cur);
    if (existing != null) return existing;
    Node clone = new Node(cur.val);
    copy.put(cur, clone);
    for (Node nb : cur.neighbors) clone.neighbors.add(dfs(nb, copy));
    return clone;
}

def clone_graph(node):
    copy = {}
    def dfs(cur):
        existing = copy.get(cur)
        if existing is not None: return existing
        clone = Node(cur.val)
        copy[cur] = clone
        for nb in cur.neighbors: clone.neighbors.append(dfs(nb))
        return clone
    return None if node is None else dfs(node)

function cloneGraph(node: GraphNode | null): GraphNode | null {
  const copy = new Map<GraphNode, GraphNode>();
  const dfs = (cur: GraphNode): GraphNode => {
    const existing = copy.get(cur);
    if (existing !== undefined) return existing;
    const clone = new GraphNode(cur.val);
    copy.set(cur, clone);
    for (const nb of cur.neighbors) clone.neighbors.push(dfs(nb));
    return clone;
  };
  return node === null ? null : dfs(node);
}

Flaws & bottlenecks

Recursion depth can reach V for a long chain of nodes, risking stack overflow on very large graphs.
The table must be filled BEFORE recursing into neighbours; moving that line below the loop causes infinite recursion.
The result can be correct only if node identity (not value) is the table key.

Interviewer cross-questions

Why must the clone be registered before visiting neighbours?

Say: A neighbour can point back to this node. If the clone is not yet in the table, the neighbour would start copying this node again, and the recursion would never end.

How deep can recursion go?

Say: Up to the number of nodes for a path-shaped graph. The problem limits nodes to 100, but a general solution should use an explicit stack for huge graphs.

Does the table key matter?

Say: Yes: use the node object itself (identity). Keying by value works only when values are unique, which this problem guarantees.

4 · expert

Iterative DFS, array indexed by value

time O(V + E)space O(V)

Use an explicit stack and an array where index v holds the clone of the node whose value is v. A node is pushed once, when its clone is first created. No recursion and no hash table.

Node* cloneGraph(Node* node) {
    if (node == nullptr) return nullptr;
    vector<Node*> copies(101, nullptr);
    Node* root = new Node(node->val);
    copies[node->val] = root;
    vector<Node*> stack = {node};
    while (!stack.empty()) {
        Node* cur = stack.back(); stack.pop_back();
        Node* clone = copies[cur->val];
        for (Node* nb : cur->neighbors) {
            Node* nbClone = copies[nb->val];
            if (nbClone == nullptr) {
                nbClone = new Node(nb->val);
                copies[nb->val] = nbClone;
                stack.push_back(nb);
            }
            clone->neighbors.push_back(nbClone);
        }
    }
    return root;
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Node[] copies = new Node[101];
    Node root = new Node(node.val);
    copies[node.val] = root;
    Deque<Node> stack = new ArrayDeque<>(); stack.push(node);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        Node clone = copies[cur.val];
        for (Node nb : cur.neighbors) {
            Node nbClone = copies[nb.val];
            if (nbClone == null) {
                nbClone = new Node(nb.val);
                copies[nb.val] = nbClone;
                stack.push(nb);
            }
            clone.neighbors.add(nbClone);
        }
    }
    return root;
}

def clone_graph(node):
    if node is None: return None
    copies = [None] * 101
    root = Node(node.val)
    copies[node.val] = root
    stack = [node]
    while stack:
        cur = stack.pop()
        clone = copies[cur.val]
        for nb in cur.neighbors:
            nb_clone = copies[nb.val]
            if nb_clone is None:
                nb_clone = Node(nb.val)
                copies[nb.val] = nb_clone
                stack.append(nb)
            clone.neighbors.append(nb_clone)
    return root

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const copies: (GraphNode | undefined)[] = new Array(101);
  const root = new GraphNode(node.val);
  copies[node.val] = root;
  const stack: GraphNode[] = [node];
  while (stack.length > 0) {
    const cur = stack.pop()!;
    const clone = copies[cur.val]!;
    for (const nb of cur.neighbors) {
      let nbClone = copies[nb.val];
      if (nbClone === undefined) {
        nbClone = new GraphNode(nb.val);
        copies[nb.val] = nbClone;
        stack.push(nb);
      }
      clone.neighbors.push(nbClone);
    }
  }
  return root;
}

Flaws & bottlenecks

Relies on values being unique and within a small known range (1 to 100); with arbitrary values you must fall back to a hash table keyed by node.
The array has fixed size; a production version would size it from the data or validate the range.
Less general than the identity-keyed table, so it is easy to misuse on other inputs.

Interviewer cross-questions

Why is it safe to use the value as the key?

Say: The problem guarantees each node has a unique value from 1 to 100. A unique small integer key is as good as identity, and an array lookup is faster than hashing.

Why push a node only when its clone is first created?

Say: Each node then enters the stack exactly once, so its neighbours are processed exactly once, even though neighbours are looked at from both ends of every edge.

What would you change for node values beyond a small range?

Say: Replace the array with a hash map keyed by node identity. The algorithm is otherwise identical.

Synchronized code walkthrough

Showing: Three passes: collect, create, wire — shares the player above; click any step to jump.

Node* cloneGraph(Node* node) {
    if (node == nullptr) return nullptr;
    vector<Node*> all;
    unordered_set<Node*> seen;
    vector<Node*> stack = {node};
    seen.insert(node);
    while (!stack.empty()) {
        Node* cur = stack.back(); stack.pop_back();
        all.push_back(cur);
        for (Node* nb : cur->neighbors) {
            if (!seen.count(nb)) {
                seen.insert(nb);
                stack.push_back(nb);
            }
        }
    }
    unordered_map<Node*, Node*> copy;
    for (Node* old : all) copy[old] = new Node(old->val);
    for (Node* old : all) {
        for (Node* nb : old->neighbors) copy[old]->neighbors.push_back(copy[nb]);
    }
    return copy[node];
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    List<Node> all = new ArrayList<>();
    Set<Node> seen = new HashSet<>();
    Deque<Node> stack = new ArrayDeque<>(); stack.push(node);
    seen.add(node);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        all.add(cur);
        for (Node nb : cur.neighbors) {
            if (!seen.contains(nb)) {
                seen.add(nb);
                stack.push(nb);
            }
        }
    }
    Map<Node, Node> copy = new HashMap<>();
    for (Node old : all) copy.put(old, new Node(old.val));
    for (Node old : all) {
        for (Node nb : old.neighbors) copy.get(old).neighbors.add(copy.get(nb));
    }
    return copy.get(node);
}

def clone_graph(node):
    if node is None: return None
    all_nodes = []
    seen = set()
    stack = [node]
    seen.add(node)
    while stack:
        cur = stack.pop()
        all_nodes.append(cur)
        for nb in cur.neighbors:
            if nb not in seen:
                seen.add(nb)
                stack.append(nb)
    copy = {}
    for old in all_nodes: copy[old] = Node(old.val)
    for old in all_nodes:
        for nb in old.neighbors: copy[old].neighbors.append(copy[nb])
    return copy[node]

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const all: GraphNode[] = [];
  const seen = new Set<GraphNode>();
  const stack: GraphNode[] = [node];
  seen.add(node);
  while (stack.length > 0) {
    const cur = stack.pop()!;
    all.push(cur);
    for (const nb of cur.neighbors) {
      if (!seen.has(nb)) {
        seen.add(nb);
        stack.push(nb);
      }
    }
  }
  const copy = new Map<GraphNode, GraphNode>();
  for (const old of all) copy.set(old, new GraphNode(old.val));
  for (const old of all) {
    for (const nb of old.neighbors) copy.get(old)!.neighbors.push(copy.get(nb)!);
  }
  return copy.get(node)!;
}

Node* cloneGraph(Node* node) {
    if (node == nullptr) return nullptr;
    unordered_map<Node*, Node*> copy; copy[node] = new Node(node->val);
    queue<Node*> q; q.push(node);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        for (Node* nb : cur->neighbors) {
            if (!copy.count(nb)) {
                copy[nb] = new Node(nb->val);
                q.push(nb);
            }
            copy[cur]->neighbors.push_back(copy[nb]);
        }
    }
    return copy[node];
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> copy = new HashMap<>(); copy.put(node, new Node(node.val));
    Queue<Node> queue = new ArrayDeque<>(); queue.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node nb : cur.neighbors) {
            if (!copy.containsKey(nb)) {
                copy.put(nb, new Node(nb.val));
                queue.add(nb);
            }
            copy.get(cur).neighbors.add(copy.get(nb));
        }
    }
    return copy.get(node);
}

def clone_graph(node):
    if node is None: return None
    copy = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for nb in cur.neighbors:
            if nb not in copy:
                copy[nb] = Node(nb.val)
                queue.append(nb)
            copy[cur].neighbors.append(copy[nb])
    return copy[node]

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const copy = new Map<GraphNode, GraphNode>([[node, new GraphNode(node.val)]]);
  const queue: GraphNode[] = [node];
  while (queue.length > 0) {
    const cur = queue.shift()!;
    for (const nb of cur.neighbors) {
      if (!copy.has(nb)) {
        copy.set(nb, new GraphNode(nb.val));
        queue.push(nb);
      }
      copy.get(cur)!.neighbors.push(copy.get(nb)!);
    }
  }
  return copy.get(node)!;
}

Node* cloneGraph(Node* node) {
    unordered_map<Node*, Node*> copy;
    function<Node*(Node*)> dfs = [&](Node* cur) -> Node* {
        auto existing = copy.find(cur);
        if (existing != copy.end()) return existing->second;
        Node* clone = new Node(cur->val);
        copy[cur] = clone;
        for (Node* nb : cur->neighbors) clone->neighbors.push_back(dfs(nb));
        return clone;
    };
    return node == nullptr ? nullptr : dfs(node);
}

public Node cloneGraph(Node node) {
    Map<Node, Node> copy = new HashMap<>();
    return node == null ? null : dfs(node, copy);
}
private Node dfs(Node cur, Map<Node, Node> copy) {
    Node existing = copy.get(cur);
    if (existing != null) return existing;
    Node clone = new Node(cur.val);
    copy.put(cur, clone);
    for (Node nb : cur.neighbors) clone.neighbors.add(dfs(nb, copy));
    return clone;
}

def clone_graph(node):
    copy = {}
    def dfs(cur):
        existing = copy.get(cur)
        if existing is not None: return existing
        clone = Node(cur.val)
        copy[cur] = clone
        for nb in cur.neighbors: clone.neighbors.append(dfs(nb))
        return clone
    return None if node is None else dfs(node)

function cloneGraph(node: GraphNode | null): GraphNode | null {
  const copy = new Map<GraphNode, GraphNode>();
  const dfs = (cur: GraphNode): GraphNode => {
    const existing = copy.get(cur);
    if (existing !== undefined) return existing;
    const clone = new GraphNode(cur.val);
    copy.set(cur, clone);
    for (const nb of cur.neighbors) clone.neighbors.push(dfs(nb));
    return clone;
  };
  return node === null ? null : dfs(node);
}

Node* cloneGraph(Node* node) {
    if (node == nullptr) return nullptr;
    vector<Node*> copies(101, nullptr);
    Node* root = new Node(node->val);
    copies[node->val] = root;
    vector<Node*> stack = {node};
    while (!stack.empty()) {
        Node* cur = stack.back(); stack.pop_back();
        Node* clone = copies[cur->val];
        for (Node* nb : cur->neighbors) {
            Node* nbClone = copies[nb->val];
            if (nbClone == nullptr) {
                nbClone = new Node(nb->val);
                copies[nb->val] = nbClone;
                stack.push_back(nb);
            }
            clone->neighbors.push_back(nbClone);
        }
    }
    return root;
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Node[] copies = new Node[101];
    Node root = new Node(node.val);
    copies[node.val] = root;
    Deque<Node> stack = new ArrayDeque<>(); stack.push(node);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        Node clone = copies[cur.val];
        for (Node nb : cur.neighbors) {
            Node nbClone = copies[nb.val];
            if (nbClone == null) {
                nbClone = new Node(nb.val);
                copies[nb.val] = nbClone;
                stack.push(nb);
            }
            clone.neighbors.add(nbClone);
        }
    }
    return root;
}

def clone_graph(node):
    if node is None: return None
    copies = [None] * 101
    root = Node(node.val)
    copies[node.val] = root
    stack = [node]
    while stack:
        cur = stack.pop()
        clone = copies[cur.val]
        for nb in cur.neighbors:
            nb_clone = copies[nb.val]
            if nb_clone is None:
                nb_clone = Node(nb.val)
                copies[nb.val] = nb_clone
                stack.append(nb)
            clone.neighbors.append(nb_clone)
    return root

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const copies: (GraphNode | undefined)[] = new Array(101);
  const root = new GraphNode(node.val);
  copies[node.val] = root;
  const stack: GraphNode[] = [node];
  while (stack.length > 0) {
    const cur = stack.pop()!;
    const clone = copies[cur.val]!;
    for (const nb of cur.neighbors) {
      let nbClone = copies[nb.val];
      if (nbClone === undefined) {
        nbClone = new GraphNode(nb.val);
        copies[nb.val] = nbClone;
        stack.push(nb);
      }
      clone.neighbors.push(nbClone);
    }
  }
  return root;
}