Clone Graph

Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a neighbors list (List[Node]).

What to notice first

• You need to create new nodes for the clone, not reuse original nodes.
• Use a visited map to track which nodes have been cloned to avoid infinite loops.
• Maintain a mapping from original nodes to cloned nodes.

Examples

Input	Output	Explanation
[[2,4],[1,3],[2,4],[1,3]]	Cloned graph	Same structure but different node objects

Constraints

• The number of nodes in the graph is in the range [1, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no self-loops and no multi-edges in the graph.

Real-World Applications

Where this pattern appears

• Database replication — deep copying complex structures.
• Undo/redo systems — storing graph snapshots.
• Game state management — cloning game world graphs.

Complexity Comparison

Approach	Time	Space	Notes
DFS	O(n + e)	O(n)	Recursive traversal with hashmap
BFS	O(n + e)	O(n)	Queue-based with hashmap

* n = number of nodes, e = number of edges

Which approach should you learn first?

• Pick DFS for recursive, intuitive solution.
• Pick BFS for iterative approach and queue understanding.

Most Intuitive

DFS

O(n + e) time · O(n) space

Iterative

BFS

O(n + e) time · O(n) space

Approach 1: DFS — Recommended

★ Recommended

Use recursive DFS to traverse the original graph while creating new nodes and mapping old to new.

⏱ Time O(n + e) Visit each node and edge once 💾 Space O(n) Hashmap for cloned nodes

Solution Code

Python

clone_graph_dfs.py

from typing import Optional
from collections import defaultdict

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

def cloneGraphDFS(node: Optional['Node']) -> Optional['Node']:
    """
    DFS approach - recursively clone nodes and build adjacency.
    Time: O(n + e)
    Space: O(n)
    """
    if not node:
        return None

    visited = {}

    def dfs(original: 'Node') -> 'Node':
        if original.val in visited:
            return visited[original.val]

        cloned = Node(original.val)
        visited[original.val] = cloned

        for neighbor in original.neighbors:
            cloned.neighbors.append(dfs(neighbor))

        return cloned

    return dfs(node)

C++

clone_graph_dfs.cpp

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node(int _val = 0) { val = _val; }
};

class Solution {
public:
    Node* cloneGraphDFS(Node* node) {
        if (!node) return nullptr;
        unordered_map<int, Node*> visited;
        return dfs(node, visited);
    }

private:
    Node* dfs(Node* node, unordered_map<int, Node*>& visited) {
        if (visited.count(node->val)) return visited[node->val];

        Node* cloned = new Node(node->val);
        visited[node->val] = cloned;

        for (Node* neighbor : node->neighbors) {
            cloned->neighbors.push_back(dfs(neighbor, visited));
        }

        return cloned;
    }
};

Java

CloneGraphDFS.java

class Node {
    public int val;
    public List<Node> neighbors = new ArrayList<Node>();
    public Node() { }
    public Node(int _val) { val = _val; }
}

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Integer, Node> visited = new HashMap<>();
        return dfs(node, visited);
    }

    private Node dfs(Node node, Map<Integer, Node> visited) {
        if (visited.containsKey(node.val)) {
            return visited.get(node.val);
        }

        Node cloned = new Node(node.val);
        visited.put(node.val, cloned);

        for (Node neighbor : node.neighbors) {
            cloned.neighbors.add(dfs(neighbor, visited));
        }

        return cloned;
    }
}

JavaScript

clone_graph_dfs.js

class Node {
    constructor(val = 0, neighbors = []) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

function cloneGraphDFS(node) {
    if (!node) return null;

    const visited = new Map();

    const dfs = (original) => {
        if (visited.has(original.val)) {
            return visited.get(original.val);
        }

        const cloned = new Node(original.val);
        visited.set(original.val, cloned);

        for (const neighbor of original.neighbors) {
            cloned.neighbors.push(dfs(neighbor));
        }

        return cloned;
    };

    return dfs(node);
}

Rust

clone_graph_dfs.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub neighbors: Vec<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            neighbors: Vec::new(),
        }
    }
}

fn cloneGraphDFS(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
    match node {
        None => None,
        Some(n) => {
            let mut visited = HashMap::new();
            Some(dfs(n, &mut visited))
        }
    }
}

fn dfs(
    node: Rc<RefCell<Node>>,
    visited: &mut HashMap<i32, Rc<RefCell<Node>>>,
) -> Rc<RefCell<Node>> {
    let val = node.borrow().val;

    if let Some(cloned) = visited.get(&val) {
        return Rc::clone(cloned);
    }

    let cloned = Rc::new(RefCell::new(Node::new(val)));
    visited.insert(val, Rc::clone(&cloned));

    let neighbors = node.borrow().neighbors.iter().map(|n| dfs(Rc::clone(n), visited)).collect();
    cloned.borrow_mut().neighbors = neighbors;

    cloned
}

Go

clone_graph_dfs.go

package main

type Node struct {
    Val       int
    Neighbors []*Node
}

func cloneGraphDFS(node *Node) *Node {
    if node == nil {
        return nil
    }

    visited := make(map[int]*Node)
    return dfsDFS(node, visited)
}

func dfsDFS(node *Node, visited map[int]*Node) *Node {
    if cloned, ok := visited[node.Val]; ok {
        return cloned
    }

    cloned := &Node{Val: node.Val}
    visited[node.Val] = cloned

    for _, neighbor := range node.Neighbors {
        cloned.Neighbors = append(cloned.Neighbors, dfsDFS(neighbor, visited))
    }

    return cloned
}

Approach 2: BFS

✓ Simple

Use queue-based BFS to iterate through the original graph while cloning nodes.

⏱ Time O(n + e) Visit each node and edge once 💾 Space O(n) Queue + hashmap

Solution Code

Python

clone_graph_bfs.py

from typing import Optional
from collections import deque

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

def cloneGraphBFS(node: Optional['Node']) -> Optional['Node']:
    """
    BFS approach - iterate through nodes using queue.
    Time: O(n + e)
    Space: O(n)
    """
    if not node:
        return None

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

    while queue:
        original = queue.popleft()
        cloned = visited[original.val]

        for neighbor in original.neighbors:
            if neighbor.val not in visited:
                visited[neighbor.val] = Node(neighbor.val)
                queue.append(neighbor)
            cloned.neighbors.append(visited[neighbor.val])

    return visited[node.val]

C++

clone_graph_bfs.cpp

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node(int _val = 0) { val = _val; }
};

class Solution {
public:
    Node* cloneGraphBFS(Node* node) {
        if (!node) return nullptr;

        unordered_map<int, Node*> visited;
        queue<Node*> q;
        q.push(node);
        visited[node->val] = new Node(node->val);

        while (!q.empty()) {
            Node* curr = q.front();
            q.pop();

            for (Node* neighbor : curr->neighbors) {
                if (!visited.count(neighbor->val)) {
                    visited[neighbor->val] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                visited[curr->val]->neighbors.push_back(visited[neighbor->val]);
            }
        }

        return visited[node->val];
    }
};

Java

CloneGraphBFS.java

class Node {
    public int val;
    public List<Node> neighbors = new ArrayList<Node>();
    public Node() { }
    public Node(int _val) { val = _val; }
}

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Integer, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        visited.put(node.val, new Node(node.val));

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            for (Node neighbor : curr.neighbors) {
                if (!visited.containsKey(neighbor.val)) {
                    visited.put(neighbor.val, new Node(neighbor.val));
                    queue.offer(neighbor);
                }
                visited.get(curr.val).neighbors.add(visited.get(neighbor.val));
            }
        }

        return visited.get(node.val);
    }
}

JavaScript

clone_graph_bfs.js

class Node {
    constructor(val = 0, neighbors = []) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

function cloneGraphBFS(node) {
    if (!node) return null;

    const visited = new Map();
    const queue = [node];
    visited.set(node.val, new Node(node.val));

    while (queue.length > 0) {
        const curr = queue.shift();

        for (const neighbor of curr.neighbors) {
            if (!visited.has(neighbor.val)) {
                visited.set(neighbor.val, new Node(neighbor.val));
                queue.push(neighbor);
            }
            visited.get(curr.val).neighbors.push(visited.get(neighbor.val));
        }
    }

    return visited.get(node.val);
}

Rust

clone_graph_bfs.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::{HashMap, VecDeque};

#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub neighbors: Vec<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            neighbors: Vec::new(),
        }
    }
}

fn cloneGraphBFS(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
    match node {
        None => None,
        Some(n) => {
            let mut visited = HashMap::new();
            let mut queue = VecDeque::new();

            let val = n.borrow().val;
            let cloned = Rc::new(RefCell::new(Node::new(val)));
            visited.insert(val, Rc::clone(&cloned));
            queue.push_back(n);

            while let Some(curr) = queue.pop_front() {
                let neighbors = curr.borrow().neighbors.iter().map(|n| Rc::clone(n)).collect::<Vec<_>>();

                for neighbor in neighbors {
                    let nval = neighbor.borrow().val;
                    if !visited.contains_key(&nval) {
                        let cloned_neighbor = Rc::new(RefCell::new(Node::new(nval)));
                        visited.insert(nval, Rc::clone(&cloned_neighbor));
                        queue.push_back(neighbor);
                    }
                    visited.get(&curr.borrow().val).unwrap().borrow_mut().neighbors.push(Rc::clone(visited.get(&nval).unwrap()));
                }
            }

            Some(visited.get(&n.borrow().val).unwrap().clone())
        }
    }
}

Go

clone_graph_bfs.go

package main

type Node struct {
    Val       int
    Neighbors []*Node
}

func cloneGraphBFS(node *Node) *Node {
    if node == nil {
        return nil
    }

    visited := make(map[int]*Node)
    queue := []*Node{node}
    visited[node.Val] = &Node{Val: node.Val}

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]

        for _, neighbor := range curr.Neighbors {
            if _, ok := visited[neighbor.Val]; !ok {
                visited[neighbor.Val] = &Node{Val: neighbor.Val}
                queue = append(queue, neighbor)
            }
            visited[curr.Val].Neighbors = append(visited[curr.Val].Neighbors, visited[neighbor.Val])
        }
    }

    return visited[node.Val]
}

Related Problems

• Number of Islands ↗ Medium #200
• Course Schedule ↗ Medium #207

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes

← Previous
#130 Surrounded Regions Next
#399 Evaluate Division →