# LeetCode 133: Clone Graph

## Problem Restatement

We are given a reference to a node in a connected undirected graph.

Each node has:

| Field | Meaning |
|---|---|
| `val` | Integer value of the node |
| `neighbors` | List of neighboring node references |

We need to return a deep copy of the graph.

A deep copy means:

1. Every original node gets a new node object.
2. Every edge is copied between the new node objects.
3. No cloned node should point back to an original node.

If the input node is `None`, return `None`.

LeetCode represents test cases using an adjacency list. The given node is the node with `val = 1`, and each node value is unique. The graph is connected, has no repeated edges, and has no self-loops.

## Examples

Example 1:

```python
adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]
```

This means:

| Node | Neighbors |
|---:|---|
| `1` | `2`, `4` |
| `2` | `1`, `3` |
| `3` | `2`, `4` |
| `4` | `1`, `3` |

The cloned graph should have the same structure:

```python
[[2, 4], [1, 3], [2, 4], [1, 3]]
```

But the nodes must be new objects.

Example 2:

```python
adjList = [[]]
```

There is one node with value `1`, and it has no neighbors.

The clone is also one node with value `1` and no neighbors.

Example 3:

```python
adjList = []
```

There are no nodes.

The input node is `None`, so the output is also `None`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `node: Optional[Node]` |
| Output | A reference to the cloned version of `node` |
| Graph type | Connected undirected graph |
| Node values | Unique integers |
| Main requirement | Deep copy, not shallow copy |

Function shape:

```python
class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        ...
```

## First Thought: Copy the Current Node and Its Neighbors

A natural first idea is:

1. Create a new node with the same value.
2. For each neighbor, create a new neighbor node.
3. Continue recursively.

This fails when the graph has cycles.

For example:

```text
1 -- 2
```

Node `1` points to node `2`.

Node `2` points back to node `1`.

If we clone recursively without remembering visited nodes, we get:

```text
clone 1
  clone 2
    clone 1
      clone 2
        ...
```

This never ends.

We need a way to remember which original nodes have already been cloned.

## Key Insight

Use a hash map:

```python
old_to_new = {}
```

The key is an original node.

The value is its cloned node.

```text
original node -> cloned node
```

This map solves two problems:

1. It prevents infinite recursion in cyclic graphs.
2. It ensures every original node corresponds to exactly one cloned node.

The important step is to insert a node into the map immediately after creating its clone, before cloning its neighbors.

That way, if the graph points back to the same node, we can return the clone that already exists.

## DFS Algorithm

Define a helper:

```python
dfs(node)
```

It returns the cloned version of `node`.

For each call:

1. If `node` is `None`, return `None`.
2. If `node` already exists in `old_to_new`, return the existing clone.
3. Create a new node with the same value.
4. Store it in `old_to_new`.
5. Recursively clone every neighbor.
6. Append cloned neighbors to the new node.
7. Return the cloned node.

## Correctness

Every time DFS sees an original node for the first time, it creates exactly one cloned node with the same value and stores the mapping.

If DFS later reaches the same original node again through another path, it returns the already-created clone. Therefore, each original node maps to one unique cloned node.

For every original edge from `node` to `neighbor`, the algorithm appends `dfs(neighbor)` to the cloned node's neighbor list. Since `dfs(neighbor)` returns the cloned version of `neighbor`, every original edge is reproduced between cloned nodes.

The graph is connected, so starting from the given node reaches every node in the graph. Therefore, the algorithm clones every node and every neighbor relationship reachable from the input node.

The returned node is the cloned version of the input node, and the whole reachable graph is a deep copy.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `V` | Number of nodes |
| `E` | Number of edges |

Each node is cloned once.

Each neighbor reference is processed once. In an undirected graph, every edge appears in two neighbor lists.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(V + E)` | Visit all nodes and neighbor references |
| Space | `O(V)` | Hash map plus recursion stack |

## Implementation

```python
# Definition for a Node.
# class Node:
#     def __init__(self, val = 0, neighbors = None):
#         self.val = val
#         self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        old_to_new = {}

        def dfs(curr: "Node") -> "Node":
            if curr is None:
                return None

            if curr in old_to_new:
                return old_to_new[curr]

            clone = Node(curr.val)
            old_to_new[curr] = clone

            for neighbor in curr.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone

        return dfs(node)
```

## Code Explanation

The map stores original-to-clone relationships:

```python
old_to_new = {}
```

When the helper receives `None`, it returns `None`:

```python
if curr is None:
    return None
```

This handles the empty graph case.

If the current node has already been cloned, return its clone:

```python
if curr in old_to_new:
    return old_to_new[curr]
```

This prevents infinite recursion and duplicate cloned nodes.

Create the clone:

```python
clone = Node(curr.val)
```

Store it immediately:

```python
old_to_new[curr] = clone
```

This timing matters. In a cycle, a neighbor may point back to this node. Because the clone is already in the map, the recursive call can reuse it.

Then clone all neighbors:

```python
for neighbor in curr.neighbors:
    clone.neighbors.append(dfs(neighbor))
```

Each appended neighbor is a cloned node, not an original node.

Finally:

```python
return dfs(node)
```

returns the cloned version of the input node.

## Iterative BFS Version

DFS is concise. BFS also works.

BFS first creates the clone for the starting node, then walks through the graph with a queue.

```python
from collections import deque

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        if node is None:
            return None

        old_to_new = {node: Node(node.val)}
        queue = deque([node])

        while queue:
            curr = queue.popleft()

            for neighbor in curr.neighbors:
                if neighbor not in old_to_new:
                    old_to_new[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)

                old_to_new[curr].neighbors.append(old_to_new[neighbor])

        return old_to_new[node]
```

This version avoids recursion depth concerns.

## Testing

LeetCode provides the `Node` class and graph serializer. For local testing, we can build a small graph manually.

```python
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def serialize(node: Node | None) -> list[list[int]]:
    if node is None:
        return []

    seen = {}
    queue = [node]
    seen[node] = True
    nodes = []

    while queue:
        curr = queue.pop(0)
        nodes.append(curr)

        for neighbor in curr.neighbors:
            if neighbor not in seen:
                seen[neighbor] = True
                queue.append(neighbor)

    nodes.sort(key=lambda x: x.val)

    return [
        sorted(neighbor.val for neighbor in curr.neighbors)
        for curr in nodes
    ]

def run_tests():
    s = Solution()

    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)

    n1.neighbors = [n2, n4]
    n2.neighbors = [n1, n3]
    n3.neighbors = [n2, n4]
    n4.neighbors = [n1, n3]

    clone = s.cloneGraph(n1)

    assert serialize(clone) == [[2, 4], [1, 3], [2, 4], [1, 3]]
    assert clone is not n1
    assert clone.neighbors[0] is not n2

    single = Node(1)
    single_clone = s.cloneGraph(single)

    assert serialize(single_clone) == [[]]
    assert single_clone is not single

    assert s.cloneGraph(None) is None

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Four-node cycle | Confirms cycles and neighbor links are cloned correctly |
| Object identity checks | Confirms deep copy, not shallow copy |
| Single node | Handles graph with no edges |
| Empty graph | Handles `None` input |