Stage 2: Recursive Thinking·Graphs: BFS & DFS

Medium#1336 min readGraphsBFSDFSHashMapLeetCode

Clone Graph

BFS/DFS with a visited map from original → clone

BFS/DFS with a visited HashMap that maps old → new nodes.

Published Apr 16, 2026

Problem

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Every node has an integer val and a list of neighbors. Two nodes with the same val are still considered distinct.

Input

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

Output

[[2, 4], [1, 3], [2, 4], [1, 3]]

Explanation

A 4-node square. The returned graph has the same adjacency but brand-new node objects.

Input

adjList = [[]]

Output

[[]]

Explanation

Single node, no neighbors.

Input

adjList = []

Output

[]

Explanation

No nodes.

Intuition

Two things to track during the walk:

Which original nodes have I already cloned? — to avoid infinite loops and duplicate work in cyclic graphs.
What's the clone of each original node? — to wire up the new neighbors lists.

One hash map answers both: map[original] = clone. The first time you meet an original node, create its clone and put it in the map. The next time, return the existing clone.

Traversal order (BFS vs DFS) doesn't matter for correctness — they both visit every node exactly once, build every edge exactly twice (once per endpoint, one time each direction), and produce the same clone.

Approach

BFS with original → clone map

TimeO(V+E)

SpaceO(V)

Recommended

Start by cloning the input node, map it, queue it. Pop originals; for each neighbor, create-and-map the clone if new, then push the clone's reference into the current clone's neighbor list.

// NOTE: LeetCode's `cloneGraph` uses a custom `Node` type; on Playground we
// define it inline. We use Rc<RefCell<Node>> to allow cycles without arena
// overhead, matching LeetCode's expected shape.
use std::cell::RefCell;
use std::collections::{HashMap, VecDeque};
use std::rc::Rc;

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

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

impl Solution {
    pub fn clone_graph(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        let root = node?;
        let mut map: HashMap<*const RefCell<Node>, Rc<RefCell<Node>>> = HashMap::new();
        let root_clone = Node::new(root.borrow().val);
        map.insert(Rc::as_ptr(&root), Rc::clone(&root_clone));
        let mut q: VecDeque<Rc<RefCell<Node>>> = VecDeque::new();
        q.push_back(Rc::clone(&root));
        while let Some(orig) = q.pop_front() {
            let orig_key = Rc::as_ptr(&orig);
            let clone = Rc::clone(&map[&orig_key]);
            let neighbors: Vec<Rc<RefCell<Node>>> =
                orig.borrow().neighbors.iter().map(Rc::clone).collect();
            for n in neighbors {
                let k = Rc::as_ptr(&n);
                let n_clone = match map.get(&k) {
                    Some(c) => Rc::clone(c),
                    None => {
                        let c = Node::new(n.borrow().val);
                        map.insert(k, Rc::clone(&c));
                        q.push_back(n);
                        c
                    }
                };
                clone.borrow_mut().neighbors.push(n_clone);
            }
        }
        Some(root_clone)
    }
}

Rust · runnable

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

function cloneGraph(node: Node | null): Node | null {
  if (node === null) return null;
  const map = new Map<Node, Node>();
  const clone = new Node(node.val);
  map.set(node, clone);
  const q: Node[] = [node];
  while (q.length > 0) {
    const orig = q.shift()!;
    const copy = map.get(orig)!;
    for (const n of orig.neighbors) {
      let nCopy = map.get(n);
      if (!nCopy) {
        nCopy = new Node(n.val);
        map.set(n, nCopy);
        q.push(n);
      }
      copy.neighbors.push(nCopy);
    }
  }
  return clone;
}

TypeScript · runnable

DFS with memoization

TimeO(V+E)

SpaceO(V)

Recursive variant. dfs(node) returns the clone; on entry, check the map and return the existing clone if present. Otherwise create a clone, map it, then recurse into each neighbor and push their clones into the new node's neighbors.

Shorter code, but the recursion can blow the stack on long chain-shaped inputs (100k nodes in a line).

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

impl Solution {
    pub fn clone_graph(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        fn dfs(
            n: &Rc<RefCell<Node>>,
            map: &mut HashMap<*const RefCell<Node>, Rc<RefCell<Node>>>,
        ) -> Rc<RefCell<Node>> {
            let key = Rc::as_ptr(n);
            if let Some(c) = map.get(&key) {
                return Rc::clone(c);
            }
            let clone = Node::new(n.borrow().val);
            map.insert(key, Rc::clone(&clone));
            let neighbors: Vec<Rc<RefCell<Node>>> =
                n.borrow().neighbors.iter().map(Rc::clone).collect();
            for nb in neighbors {
                let nb_clone = dfs(&nb, map);
                clone.borrow_mut().neighbors.push(nb_clone);
            }
            clone
        }
        let root = node?;
        let mut map = HashMap::new();
        Some(dfs(&root, &mut map))
    }
}

Rust · runnable

function cloneGraph(node: Node | null): Node | null {
  if (node === null) return null;
  const map = new Map<Node, Node>();
  const dfs = (n: Node): Node => {
    const existing = map.get(n);
    if (existing) return existing;
    const clone = new Node(n.val);
    map.set(n, clone);
    for (const nb of n.neighbors) clone.neighbors.push(dfs(nb));
    return clone;
  };
  return dfs(node);
}

TypeScript · runnable

Trace

BFS on adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]:

  1 --- 2
  |     |
  4 --- 3

step	queue (originals)	map size	action
start	[1]	1	seed map with 1 → 1'
1	[2, 4]	3	pop 1, create 2' and 4', wire 1'→[2',4']
2	[4, 3]	4	pop 2, create 3' (4' exists), wire 2'→[1',3']
3	[3]	4	pop 4, no new clones, wire 4'→[1',3']
4	[]	4	pop 3, no new clones, wire 3'→[2',4']

Result: 4 new nodes, same adjacency, zero pointers back into the original graph.

Edge cases

Null input — return null.
Single node with no edges — map has 1 entry, return its clone.
Cycles — the map prevents re-cloning; each node is created exactly once.
Self-loop — neighbors contains self; the clone's neighbors will also contain itself after the map lookup.

Takeaway

"Deep clone" generalizes beyond graphs — it's identity-preserving traversal. Anything with shared references (linked list with random pointer, DAG of tasks, tree of configurations) follows the same pattern: walk the structure, keep a map from original to clone, dedupe by lookup. Internalize this template once and nearly every "deep copy with shared references" problem becomes mechanical.

Medium#200

Number of Islands

Flood fill with DFS. The grid IS the graph — each cell is a node.

Medium#207

Course Schedule

Cycle detection in directed graph. Both DFS (3-color) and Kahn’s BFS work.

Hard#127

Word Ladder

BFS on an implicit graph. Each word is a node, edges connect words differing by one letter.