Clone Graph: BFS/DFS with HashMap old→new

• Clone Graph – deep-copy every node in a connected undirected graph so the clone has the same structure but shares no objects with the original.
• HashMap old-to-new – maps each original node to its clone, doubling as a visited set and a clone registry.
• Insert before expand – create the clone and store it in the map before processing neighbors to break cycles.
• Traversal – DFS (recursive or stack-based) or BFS (queue-based), both using the map for termination.
• Complexity – O(V + E) time, O(V) space.

What is the Clone Graph 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 (int) and a list of neighbors. The clone must have the same structure but share no objects with the original. Cycles in the graph must be handled correctly.

package com.bank.model;

import java.util.ArrayList;
import java.util.List;

public class AccountNode {
    public int val;
    public List<AccountNode> neighbors;

    public AccountNode(int val) {
        this.val = val;
        this.neighbors = new ArrayList<>();
    }
}

How does the DFS approach work?

Use a HashMap from original node to its clone. When visiting a node, first check if it is already in the map (already cloned). If so, return the existing clone. Otherwise, create the clone, insert it into the map, then recursively clone each neighbor and add the cloned neighbors to the clone's neighbor list.

package com.bank.service;

import com.bank.model.AccountNode;
import java.util.HashMap;
import java.util.Map;

public class GraphCloner {
    private final Map<AccountNode, AccountNode> clones = new HashMap<>();

    public AccountNode cloneGraph(AccountNode node) {
        if (node == null) return null;
        if (clones.containsKey(node)) return clones.get(node);

        AccountNode copy = new AccountNode(node.val);
        clones.put(node, copy); // insert BEFORE expanding neighbors

        for (AccountNode neighbor : node.neighbors) {
            copy.neighbors.add(cloneGraph(neighbor));
        }
        return copy;
    }
}

How does the BFS approach work?

Use a queue for BFS and the same HashMap for clone tracking. Start by cloning the root node and enqueuing it. For each dequeued original node, iterate its neighbors: if a neighbor has not been cloned, clone it, store the mapping, and enqueue it. Then wire the clone's neighbor list by looking up each neighbor's clone in the map.

package com.bank.service;

import com.bank.model.AccountNode;
import java.util.*;

public class BfsGraphCloner {
    public AccountNode cloneGraph(AccountNode node) {
        if (node == null) return null;

        Map<AccountNode, AccountNode> clones = new HashMap<>();
        Queue<AccountNode> queue = new LinkedList<>();

        clones.put(node, new AccountNode(node.val));
        queue.add(node);

        while (!queue.isEmpty()) {
            AccountNode original = queue.poll();
            AccountNode copy = clones.get(original);

            for (AccountNode neighbor : original.neighbors) {
                if (!clones.containsKey(neighbor)) {
                    clones.put(neighbor, new AccountNode(neighbor.val));
                    queue.add(neighbor);
                }
                copy.neighbors.add(clones.get(neighbor));
            }
        }
        return clones.get(node);
    }
}

Why must the clone be inserted before expanding neighbors?

If you expanded neighbors first, a neighbor pointing back to the current node would find no clone in the map and recurse infinitely (DFS) or enqueue it again (BFS). Inserting the clone early ensures that any back-reference finds the clone already present, breaking the cycle.

// Wrong: expand before insert (infinite recursion on cycles)
AccountNode copy = new AccountNode(node.val);
for (AccountNode nb : node.neighbors) {
    copy.neighbors.add(cloneGraph(nb)); // nb may point back to node
}
clones.put(node, copy); // too late

// Correct: insert before expand
AccountNode copy = new AccountNode(node.val);
clones.put(node, copy); // early insert
for (AccountNode nb : node.neighbors) {
    copy.neighbors.add(cloneGraph(nb)); // back-ref finds clone
}

What is the time and space complexity?

Each node is visited once (O(V)) and each edge is processed once (O(E)), so the total time is O(V + E). The space is O(V) for the HashMap plus O(V) for the recursion stack (DFS) or queue (BFS). The cloned graph itself uses O(V + E) space.

Time:  O(V + E)  -- each node and edge processed once
Space: O(V)      -- map + stack/queue
Clone: O(V + E)  -- the copy itself

What are edge cases?

Edge cases include a null input (return null), a single node with no neighbors (clone just the one node), and a graph with self-loops (a node that neighbors itself). The map handles self-loops because the node's clone is inserted before its neighbor list is wired.

// Single node, no neighbors
AccountNode single = new AccountNode(1);
AccountNode cloned = new GraphCloner().cloneGraph(single);
System.out.println(cloned.val);              // 1
System.out.println(cloned.neighbors.size()); // 0
System.out.println(cloned != single);        // true (different object)

What are common mistakes?

The most common mistake is not inserting the clone into the map before recursing, which causes infinite loops on cyclic graphs. Another is using a visited boolean instead of a map, which means you cannot look up the clone of a previously visited node to wire its neighbors.

// Wrong: using a visited set instead of a map
Set<AccountNode> visited = new HashSet<>();
// Cannot look up the clone of a visited node

// Correct: map serves as both visited set and clone registry
Map<AccountNode, AccountNode> clones = new HashMap<>();

How is this different from cloning a linked list with random pointers?

Both problems use a map from original to clone to handle non-tree pointers. The difference is that Clone Graph handles an arbitrary undirected graph with cycles, while Copy List with Random Pointer handles a linear list with extra forward/backward pointers. The map-based technique is the same, but Clone Graph requires a full traversal (DFS/BFS) while the linked list can be walked linearly.

What should a senior engineer know?

A senior engineer knows that the map is the single source of truth for what has been cloned, that insert-before-expand is the cycle-safety invariant, and that DFS and BFS are interchangeable here with the same complexity. They also mention that for very deep graphs, BFS avoids stack overflow risks that DFS with recursion has.