Welcome to Day 11 of your coding interview journey.

Yesterday, you learned:

• ✅ Graph basics
• ✅ DFS (Depth-First Search)
• ✅ BFS (Breadth-First Search)

Today, we apply those concepts to a very common and important problem:

👉 Graph Cloning

---

🧠 What Does “Clone a Graph” Mean?

You are given a reference to a node in a graph.

👉 Your task is to create a deep copy of the entire graph.

---

⚠️ Important

A deep copy means:

• New nodes must be created
• Connections must be preserved
• No references to the original graph

---

Example Graph:

1 -- 2
|    |
4 -- 3

👉 After cloning, you should have a completely new graph with the same structure.

---

🔑 Key Challenges

Graph cloning tests your ability to:

• Traverse a graph (DFS or BFS)
• Handle cycles (very important!)
• Avoid duplicating nodes

---

💡 Core Idea

👉 Use a HashMap (dictionary) to store:

original_node -> cloned_node

This helps you:

• Avoid infinite loops
• Reuse already cloned nodes

---

💡 Approach 1 – DFS (Recursive)

---

🧠 Strategy

1. If node is already cloned → return it
2. Clone the current node
3. Recursively clone neighbors
4. Store mapping

---

🛠️ Solution in Python (DFS)

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

def clone_graph(node):
    if not node:
        return None

    clones = {}

    def dfs(curr):
        if curr in clones:
            return clones[curr]

        copy = Node(curr.val)
        clones[curr] = copy

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

        return copy

    return dfs(node)

---

⚡ Complexity (DFS)

• Time: O(V + E)
• Space: O(V)

---

💡 Approach 2 – BFS (Iterative)

---

🧠 Strategy

• Use a queue to traverse
• Clone nodes level by level

---

🛠️ Solution in Python (BFS)

from collections import deque

def clone_graph_bfs(node):
    if not node:
        return None

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

    while queue:
        curr = queue.popleft()

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

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

    return clones[node]

---

🎯 DFS vs BFS for Cloning

Approach	Style	When to Use
DFS	Recursive	Easier to write
BFS	Iterative	Avoid recursion limits

---

⚠️ Common Mistakes

• ❌ Not handling cycles → infinite recursion
• ❌ Forgetting to store visited nodes
• ❌ Creating duplicate nodes
• ❌ Returning original nodes instead of cloned ones

---

🧪 Practice Problems

To reinforce graph concepts:

1. Course schedule
2. Number of connected components
3. Reconstruct itinerary
4. Word ladder
5. Network delay time

---

🎯 Key Takeaways

• Graph cloning = Traversal + HashMap
• Always track visited nodes
• DFS and BFS both work
• Think in terms of:
  • Nodes
  • Neighbors
  • Mapping

---

🚀 Your Challenge (Day 11)

Solve this:

Clone a graph where each node also has a random pointer.

(Hint: similar idea, more mappings 😉)

---

📌 Final Thoughts

Graph cloning is a classic interview problem because it combines:

• Graph traversal
• Memory management
• Deep understanding of references

Mastering this makes you much stronger in graph problems.