24. Clone Escalation Graph

Problem

Fin's ops team wants to duplicate an existing escalation routing graph (teams as nodes, handoff edges as connections) into a sandbox environment so they can test routing changes without touching production.

Given a reference node in a connected graph, deep-copy every node reachable from it, preserving structure including cycles, and return the clone of that starting node (or None if the input is None). The clone must not share any Node objects with the original graph.

Because Node objects aren't directly comparable by value, this problem's test cases represent graphs as plain {val: [neighbor_val, ...]} adjacency dicts instead of raw Node objects. Two helpers bridge the gap: build_graph turns an adjacency dict into a live Node graph rooted at its first key (or None for an empty dict), and graphs_structurally_equal walks two graphs in lockstep, comparing vals and neighbor sets, to check the clone matches the expected shape without relying on object identity.

Source: src/24_clone_escalation_graph.py

class Node:
    def __init__(self, val: str, neighbors: list['Node'] | None = None): ...

def clone_graph(node: 'Node | None') -> 'Node | None':
    ...

>>> root = build_graph({"a": ["b"], "b": ["a"]})
>>> clone = clone_graph(root)
>>> clone is not root
True
>>> clone.val, sorted(n.val for n in clone.neighbors)
('a', ['b'])

>>> clone_graph(None) is None
True

Step-by-Step Approach

1. Handle the trivial case first: if node is None, return None.
2. Keep a map from the identity of each original node (id(original_node)) to its already-created clone. This is what lets the algorithm handle cycles: once a node has been cloned once, later references to it just look up the existing clone instead of cloning again.
3. Create the clone of the starting node immediately and store it in the map, then start a BFS (a queue of original nodes still to process) from it.
4. Pop an original node from the queue and look up its clone. For each of its neighbors: if the neighbor hasn't been cloned yet, create its clone, store it in the map, and enqueue the original neighbor for later processing; either way, append the neighbor's clone to the current clone's neighbor list.
5. Continue until the queue is empty — every reachable node has been visited exactly once and has a corresponding clone with correctly wired neighbor edges.
6. Return the clone associated with the original starting node.

The key insight is the identity-keyed visited map: it does double duty as both "have I cloned this node yet" (preventing infinite loops on cycles) and "what is this node's clone" (letting you wire up edges to already-created clones). DFS with recursion works identically; BFS with an explicit queue just avoids Python's recursion depth limit on deep graphs.

Reference solution

def clone_graph(node: 'Node | None') -> 'Node | None':
    # BFS with a visited map keyed by original node identity, O(V + E) time and space
    if node is None:
        return None
    # seed map with start node's clone
    clones: dict[int, Node] = {id(node): Node(node.val)}
    queue = [node]
    while queue:
        # FIFO -> BFS; O(n) shift, deque.popleft() would be O(1)
        current = queue.pop(0)
        current_clone = clones[id(current)]
        for neighbor in current.neighbors:
            # first sighting: clone + enqueue; else skip (cycle-safe)
            if id(neighbor) not in clones:
                clones[id(neighbor)] = Node(neighbor.val)
                queue.append(neighbor)
            # wire edge every time, unconditional
            current_clone.neighbors.append(clones[id(neighbor)])
    return clones[id(node)]

Key Functions & Tricks

• id(node) — object identity as the map key, so distinct nodes with the same val stay distinct.
• clones = {id(node): Node(node.val)} — seeds the start node's clone before traversal begins.
• queue.pop(0) — FIFO removal, giving BFS order; O(n) per call, deque.popleft() is O(1).
• id(neighbor) not in clones — cycle-safety check: clone/enqueue once, skip on repeat visits.
• current_clone.neighbors.append(...) — wires the edge unconditionally, every traversal.

How to Recognize This Pattern