Skip to main content

19. Clone Graph

mediumAsked at ServiceNow

Deep-copy a connected undirected graph where each node has a value and a list of neighbors. ServiceNow asks this because CMDB cloning — duplicating a service map with all its CI relationships intact — is a real product operation, and the hash-map-keyed-by-original-node pattern is directly applicable.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • LeetCode Discuss (2025)— Reported by ServiceNow SDE-II candidates as an onsite graph design question.
  • Blind (2026)— Mentioned as a graph question that ServiceNow pairs with a design follow-up.

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains an integer val (1 to n) and a list of its neighbors. The graph may have cycles, so you need to track already-cloned nodes to avoid infinite loops.

Constraints

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops.

Examples

Example 1

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]

Explanation: Deep copy of a 4-node cycle graph.

Example 2

Input
adjList = [[]]
Output
[[]]

Explanation: A single node with no neighbors.

Approaches

1. Recursive DFS without visited map

Recursively clone each node and its neighbors — fails on cycles because it infinitely recurses.

Time
O(infinite)
Space
O(infinite)
// BROKEN — infinite loop on any cycle
function cloneGraph(node) {
  if (!node) return null;
  const clone = new Node(node.val);
  for (const nei of node.neighbors) {
    clone.neighbors.push(cloneGraph(nei)); // infinite on cycles
  }
  return clone;
}

Tradeoff: Illustrates WHY a visited map is required — showing this broken version and then fixing it demonstrates strong reasoning.

2. DFS with clone map

Use a Map from original node to its clone. Before recursing into a neighbor, check if it's already been cloned and return the existing clone. This breaks cycles and guarantees each node is cloned exactly once.

Time
O(V + E)
Space
O(V)
function cloneGraph(node) {
  if (!node) return null;
  const cloneMap = new Map(); // original -> clone

  function dfs(original) {
    if (cloneMap.has(original)) return cloneMap.get(original);
    const clone = new Node(original.val);
    cloneMap.set(original, clone); // register BEFORE recursing
    for (const nei of original.neighbors) {
      clone.neighbors.push(dfs(nei));
    }
    return clone;
  }

  return dfs(node);
}

Tradeoff: Key insight: register the clone in the map BEFORE recursing into neighbors. This prevents re-entering a node in case of a cycle, ensuring the clone reference is reused rather than duplicated.

ServiceNow-specific tips

ServiceNow interviewers look for candidates who register the clone in the map BEFORE processing neighbors — this single ordering decision is the entire insight of the problem. Bonus signal: draw a parallel to CMDB's clone-service-map operation where a new map is created but all CI-to-CI relationship edges must point within the new map, not back to the original.

Common mistakes

  • Registering the clone in the map AFTER the recursive call — causes infinite recursion on any cycle before the registration.
  • Using node.val as the map key instead of the node reference — fails when multiple nodes could share the same val (violates the problem guarantee but interviewers test your awareness).
  • Forgetting the null check for an empty graph — returns undefined instead of null.

Follow-up questions

An interviewer at ServiceNow may pivot to one of these next:

  • Clone a graph where nodes have arbitrary attributes, not just an integer val.
  • Serialize and deserialize a graph (adjacent to LC 297 tree serialization).
  • Deep clone an object graph with circular references in JavaScript (structuredClone vs custom logic).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why must I register the clone before recursing?

Because recursing into a neighbor that eventually points back to the current node will call dfs(currentNode) again. If the current node's clone is not yet in the map, a second clone will be created — breaking the graph structure. Pre-registration ensures the first clone is reused.

Can I use BFS instead of DFS?

Yes — BFS with a queue and the same clone map is equally correct and avoids recursion depth issues. The registration-before-processing invariant is identical: add (original, clone) to the map when you first encounter a node, before pushing it into the queue.

Practice these live with InterviewChamp.AI

Drill Clone Graph and other ServiceNow interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →