intermediate8 min read·Updated October 2, 2026

Clone an Undirected Graph Explained: Tracing the 1–2–3–1 Triangle

Master graph cloning with a step-by-step walkthrough of the 1–2–3–1 triangle. Learn the hash map mental model, DFS traversal, and handle cycles.

By Learnisim AI·Published October 2, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Graph basics and adjacency lists
  • Recursion and Depth-First Search (DFS)
  • Hash maps or dictionaries
Graph Cloning & Cyclic Memory: 1—2—3—1 Triangle 1. Original Cyclic Graph 1 2 3 Trap: 1 → 2 → 3 → 1 (Infinite Loop) 2. HashMap Memory Bridge visited_map = { 1 : clone(1), 2 : clone(2), 3 : clone(3) } Prevents re-cloning & locks identity 3. Resulting Deep Copy c1 c2 c3 Safe, isolated duplicate triangle Step-by-Step Traversal & Mapping Execution Step 1: Visit Node 1 • Not in map: create clone(1) • Register: { 1: clone(1) } • Queue neighbors: [2, 3] Initializes root clone cleanly Step 2: Explore Node 2 • Not in map: create clone(2) • Register: {1:c1, 2:c2} • Wire clone(1) <—> clone(2) Expands graph structure Step 3: Handle Cycle Back • Node 2 links back to Node 1 • Map check: 1 ALREADY in map • Return existing clone(1) Breaks loop, preserves triangle
Clone 1—2—3—1 (a triangle of nodes 1,2,3) overview diagram
Why

Why copying a graph requires more than a simple loop

Phase 1: The Trap of Cyclic Copying

Imagine you are handed a graph structured as a triangle: node 1 connects to node 2, node 2 connects to node 3, and node 3 connects back to node 1. Your mission is to create a complete deep copy of this triangle so that the cloned nodes are entirely distinct from the originals. If you write a naive traversal that blindly copies nodes and their neighbors without tracking what you have already visited, you immediately hit a wall. In our triangle 1—2—3—1, starting at node 1 leads to node 2, which leads to node 3, which leads right back to node 1, triggering an infinite recursion or an endless loop.
To see why this happens, consider what happens when you try to copy node 1. It has neighbors . Copying node 2 means looking at its neighbors, which include node 1 and node 3. If your code does not remember that node 1 has already been cloned, it will instantiate a brand new clone of node 1 when visiting node 2's neighbor list, which then tries to clone node 2 again, and so on forever. Without a memory mechanism, your traversal spins out of control before it ever finishes building the first copy.
Why Copying a Cyclic Graph Requires a Visited Map The Trap of Naive Traversal in a Triangle Graph (1 — 2 — 3 — 1) Original Graph (Triangle 1—2—3) Node 1 Node 2 Node 3 Every node has 2 bidirectional neighbors. Visiting without a memory creates endless loops. NAIVE The Infinite Recursion Trap 1. Clone Node 1 (has neighbors {2, 3}) 2. Visit Node 2 → clones Node 1 again! ⚠ STACK OVERFLOW / INFINITE LOOP Calls 1 → 2 → 3 → 1's clone → 2's clone → ... The Fix: Hash Map (visited) Store { originalNode: clonedNode } before recursing
Why copying a graph requires more than a simple loop diagram
Model

The Blueprint and the Mirror: Mapping Originals to Clones

Phase 2: The Map as a Memory

When copying our triangle, we cannot rely on a naive recursive function that blindly traverses edges. Without a record of who has already been created, visiting node 2 from node 1, and then node 1 from node 2, creates an infinite loop. We need a dictionary or hash map that acts as a bridge between the old universe and the new one, mapping original_node cloned_node.
Imagine standing at node 1 of our triangle. Before we walk out to its neighbors 2 and 3, we create a blank clone of node 1 and instantly register this pair in our map. If any future path leads back to node 1, our algorithm checks the map, sees that node 1 already has a mirror, and returns the existing clone instead of spawning a duplicate.
[Original Graph] [HashMap Memory] [Cloning Process]
Node 1 (val: 1) -----> orig_1 : clone_1 -----> Create clone_1
Node 2 (val: 2) -----> orig_2 : clone_2 -----> Populate neighbors
Node 3 (val: 3) -----> orig_3 : clone_3 -----> Keep references safe
This dictionary solves both infinite recursion and identity preservation. Every node is instantiated exactly once, ensuring that when node 2 and node 3 point to node 1 in their neighbor lists, they point to the exact same cloned instance of node 1, preserving the cyclic structure of our triangle.
python
def create_clone_mapping(node, visited_map):
    # TODO: Check if node is already in visited_map
    # TODO: If not, create a new Node(node.val) and store it
    pass
The Blueprint and the Mirror: Mapping Originals to Clones Preventing infinite loops in cyclic graph cloning via a hash map bridge 1. Original Universe Cyclic Triangle (1-2-3-1) 1 2 3 The Danger of Recursion: Visiting 1 -> 2 -> 1 creates an infinite loop without memory! Check & Store 2. HashMap Memory visited_map = {} orig_1 : clone_1 exists? return ref orig_2 : clone_2 exists? return ref orig_3 : clone_3 exists? return ref O(1) Lookups: Ensures each node is cloned exactly once Mirror Ref 3. Cloned Universe Safe Cyclic Mirror c1 c2 c3 Identity Preserved: c2 and c3 point to the exact same instance of c1! Algorithm Rule: If node in map -> return map[node]. Else -> create clone, register in map, populate neighbors recursively.
The Blueprint and the Mirror: Mapping Originals to Clones diagram
Worked example

Tracing the 1—2—3—1 Triangle Clone Step-by-Step

Phase 3: Walking the Triangle

Now that we have established our blueprint mapping strategy, let's watch it execute live on our 1—2—3—1 triangle graph. We start at Node 1 with an empty hash map visited = {}. Our goal is to perform a depth-first traversal, creating clones on the fly and wiring their neighbors correctly without falling into an infinite loop.

Given

- An undirected graph consisting of three nodes forming a cycle: Node 1 Node 2, Node 2 Node 3, and Node 3 Node 1.
•Entry point: Node 1.

- HashMap tracking: (maps ).

Steps

1. Visit Node 1: It is not in . We create , put into , and inspect its neighbors: Node 2 and Node 3.
- Running : {1: clone(1)}
2. Explore Neighbor 2 of Node 1: Node 2 is not in . We create , put into , and inspect its neighbors: Node 1 and Node 3.
- Running : {1: clone(1), 2: clone(2)}
3. Explore Neighbor 1 of Node 2: Node 1 is already in . We return immediately without re-visiting or re-creating it. We push this returned reference into .
4. Explore Neighbor 3 of Node 2: Node 3 is not in . We create , put into , and inspect its neighbors: Node 2 and Node 1.
- Running : {1: clone(1), 2: clone(2), 3: clone(3)}
5. Complete the Triangle: From , we check its neighbors (Node 2 and Node 1). Both already exist in . We attach and to and unwind the recursion stack.

Result

Every node in the triangle has been instantiated exactly once and stored in our hash map. The final cloned graph structure mirrors the original triangle perfectly, and traversing never references any memory address from the original nodes.
Phase 3: Walking the 1—2—3—1 Triangle & Visited HashMap Original Graph (DFS Context) Node 1 Node 2 Node 3 Active DFS: Visiting Node 1 1 → Create clone(1) Check neighbors 2 & 3 recursively Map & Wire Hash Map & Cloned Tri-Graph visited = { original → clone } 1 : clone(1) 2 : clone(2) 3 : clone(3) All nodes fully mapped & cycle safely handled! cl(1) cl(2) cl(3) Cached lookup prevents infinite recursion loop Step 3 of 5: Walking the Triangle • No original memory addresses referenced
Tracing the 1—2—3—1 Triangle Clone Step-by-Step diagram
Practice

Practice: Walk Through Cloning a Disconnected Node

Phase 4:

Now that you have traced the standard triangle traversal, it is time to test your mental model against a slight twist. Imagine we add a fourth node, 4, which has no edges connecting it back to the triangle—it is completely isolated. Your task is to trace how our established DFS and hash map algorithm handles this disconnected extra node when starting our clone at node 1.
Recall the core algorithm steps: check if the current node is in the hash map; if not, create its clone, record it, and recursively clone its neighbors. Consider what happens to node 4 if the entry point is strictly node 1. Work through the sequence of map insertions and recursive calls to determine whether node 4 gets cloned in this traversal and why.
python
# Modified graph: Triangle (1-2-3-1) plus isolated node (4)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node1.neighbors = [node2, node3]
node2.neighbors = [node1, node3]
node3.neighbors = [node1, node2]
node4.neighbors = []
Take a moment to write down the state of your hash map after visiting all reachable nodes from node 1. Verify what happens to any components of the graph that cannot be reached from your starting reference point.
python
def trace_disconnected_node():
    # Given node1 from the 1-2-3-1 triangle with an isolated node4
    # Predict the keys present in your visited/cloned hash map after dfs(node1)
    pass
Apply

Applying Graph Cloning Patterns to N-Ary Tree Serialization

Phase 5: Applying the Pattern Beyond Undirected Graphs

The hash map tracking strategy we used to clone our 1—2—3—1 triangle is not just for undirected cyclic graphs. The exact same pattern of maintaining a reference map to prevent infinite loops and duplicate instantiations solves structural deep-copy problems in other domains, such as serializing and deserializing an -ary tree with parent pointers. When nodes point bidirectionally to both children and parents, naive tree traversals spin infinitely just like our triangle graph did.
By treating the parent-child pointers as undirected edges and storing every created node in a lookup table before recursing into its children, you guarantee that shared subtrees or circular references map cleanly to a single new instance. Whether you are cloning graph nodes or serializing complex JSON objects with internal cross-references, the core invariant remains identical: check the map first, instantiate if missing, and populate neighbors second.
python
def serialize_node(node, memo):
    if not node:
        return None
    if node in memo:
        return memo[node]
    
    clone = Node(node.val)
    memo[node] = clone
    for child in node.children:
        clone.children.append(serialize_node(child, memo))
    return clone
python
class Node:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children is not None else []

# Question: Explain how the memoization map prevents infinite recursion when serializing an N-ary tree that contains accidental cycle references between children and parents.

FAQ

How does the algorithm handle the 1–2–3–1 triangle without getting stuck in an infinite loop?
It uses a hash map to store a mapping from original nodes to their newly created clones. Before visiting or cloning any neighbor, the algorithm checks if a clone already exists in the map, immediately halting cycle traversal.
What is the time and space complexity of cloning an undirected graph?
Both time and space complexity are O(N + E), where N is the number of nodes and E is the number of edges. Every node and edge is visited and processed a constant number of times.
Can graph cloning be implemented using Breadth-First Search (BFS) instead of DFS?
Yes. BFS uses a queue alongside the same hash map to iteratively traverse and clone nodes layer by layer.

Keep learning