Clone Graph LeetCode Solution: BFS, DFS, and Hash Map

Clone Graph (#133) is one of those LeetCode problems that looks deceptively simple until you think about what "deep copy" actually means for a structure with cycles. You cannot just walk the graph and create new nodes — if two neighbors point to each other, a naive approach will loop forever or create duplicate nodes that break the structure.

This problem is a staple in coding interviews at companies like Meta, Google, and Amazon because it tests two fundamental skills simultaneously: graph traversal and reference management. If you can solve clone graph leetcode confidently, you have demonstrated that you understand how pointers and object identity work in a graph context.

The good news is that the solution pattern is elegant and reusable. Whether you choose BFS or DFS, the core idea is the same: maintain a hash map from each original node to its clone. This single data structure solves both the traversal tracking and the cloning in one pass.

You are given a reference to a node in a connected undirected graph. Each node has a value (an integer) and a list of neighbors. Your task is to return a deep copy of the entire graph — every node must be a new object, and the neighbor relationships must mirror the original exactly.

The key constraint is that the graph can contain cycles. Node A might list Node B as a neighbor, and Node B lists Node A right back. If your cloning logic follows neighbors recursively without any bookkeeping, it will bounce between A and B forever. The graph is also connected, meaning you can reach every node from the starting node.

The input uses an adjacency list representation. For example, if the input is [[2,4],[1,3],[2,4],[1,3]], node 1 connects to nodes 2 and 4, node 2 connects to nodes 1 and 3, and so on. Your output must produce a structurally identical graph with entirely new node objects.

The BFS approach to clone graph leetcode uses a queue to process nodes level by level, combined with a hash map that maps each original node to its newly created clone. You start by cloning the given node, adding it to the map, and pushing it onto the queue.

For each node you dequeue, iterate through its neighbors. If a neighbor has not been cloned yet (it is not in the hash map), create a new clone, add it to the map, and enqueue it. Whether the neighbor was just cloned or already existed in the map, append the cloned neighbor to the current clone's neighbor list.

This leetcode 133 solution runs in O(V+E) time where V is the number of nodes and E is the number of edges. Space complexity is also O(V) for the hash map and the queue. The BFS approach is particularly intuitive because it mirrors standard BFS traversal — the only addition is maintaining the clone map.

The DFS approach to clone graph BFS DFS uses recursion and the same hash map concept, but processes nodes depth-first instead of breadth-first. The recursive function takes an original node, checks if it already exists in the hash map, and if so returns the existing clone immediately — this is how cycles are handled.

If the node has not been cloned yet, create a new node with the same value, add it to the hash map immediately (before processing neighbors), and then recursively clone each neighbor. Adding the clone to the map before recursing is critical — it ensures that when a cycle brings you back to this node, the map already has an entry and the recursion terminates.

The DFS solution has the same O(V+E) time and O(V) space complexity as BFS. Some developers find DFS more elegant because the code is shorter — the recursive function naturally handles the traversal without an explicit queue. However, for very large graphs, the recursive call stack could be a concern.

The hash map is not just helpful — it is the entire reason the graph cloning algorithm works correctly. Without it, you face two catastrophic problems: infinite loops from cycles and node duplication from shared neighbors.

Consider a simple cycle: node 1 connects to node 2, and node 2 connects back to node 1. Without a map tracking which nodes have been cloned, your traversal will create a clone of node 1, then try to clone node 2, which tries to clone node 1 again, and so on forever. The hash map breaks this cycle by returning the already-created clone when a node is visited a second time.

The clone graph hash map also prevents node duplication. If nodes 2 and 3 both list node 4 as a neighbor, you need to ensure they both reference the same cloned node 4 — not two different copies. The map guarantees that each original node maps to exactly one clone, preserving the graph's identity relationships.

This pattern — using a map from original references to copies — appears throughout computer science whenever you need to deep copy a structure with shared references or cycles. It is the same principle behind serialization libraries, garbage collectors, and object graph cloners.

The first edge case is the empty graph: if the input node is null, return null immediately. This is a simple base case but forgetting it will cause a null pointer exception. Interviewers often start with this question to see if you think about boundaries.

A single node with no neighbors (or a self-loop) is another important case. Your algorithm should correctly create one cloned node with an empty neighbor list. If the single node has a self-loop — it lists itself as a neighbor — the hash map pattern handles this naturally because the clone is added to the map before processing neighbors.

A cycle between exactly two nodes (nodes 1 and 2 as mutual neighbors) is the minimal cycle case and the best one to trace through mentally or on a whiteboard. If your solution handles this case correctly, it handles all cycles. Finally, a fully connected graph where every node neighbors every other node tests that your solution scales gracefully without duplicating any clones.

Clone Graph is more than just an interview question — it teaches the fundamental pattern for deep copying any structure that contains cycles or shared references. The graph deep copy cycle pattern you learn here applies directly to Copy List with Random Pointer (#138), which uses the exact same hash map approach for a linked list with an extra pointer.

The broader lesson is that whenever you need to duplicate a structure where nodes can reference each other, you need an identity map. Trees do not require this because they are acyclic and each node has exactly one parent. Graphs break that assumption, and the hash map is the tool that restores order.

If you are preparing for coding interviews, practice Clone Graph until the hash map pattern feels automatic. Build it with BFS first since the iterative approach is easier to debug, then implement DFS to show versatility. YeetCode flashcards can help you drill the pattern recognition — seeing "deep copy" and "graph" should immediately trigger the hash map approach in your mind.