Deep Clone, Constraint by Constraint

Start from brute force

The first version most people write is plain recursion: a dict becomes {k: deep_clone(v) for k, v in value.items()}, a list becomes [deep_clone(x) for x in value], and anything else is returned as-is. It is correct for stages 1 and 2, because it builds a new container for every container it reaches, and on a tree it costs O(n) time and O(depth) stack. Stage 3 breaks it loudly: on o["self"] = o it recurses until Python raises RecursionError. Stage 4 breaks it quietly: a shared object is cloned once per reference, so c["p"] is c["q"] is False, and 20 levels that each hold two references to the next produce 2,097,151 dict copies instead of 21.

The approach

One map, consulted before recursing, fixes stages 3 and 4 together. The insight is that a cycle and a shared reference are the same event: reaching an object you have already started cloning. If a map from original to clone answers “what did I turn this into?”, returning that answer ends the cycle and keeps both shared references on one clone. The invariant: every container entered so far has exactly one clone, recorded in seen before any of its children are visited.

The reference passes seen, a dict keyed by id(value), through every call. Non-containers return immediately. For a dict or list it computes key = id(value) and returns seen[key] if present. Otherwise it creates the empty out, stores seen[key] = out first, and only then fills out by recursing into each item or value. Recording before filling is what lets a cycle find a clone that is still under construction, and keying by identity rather than by value keeps two equal but distinct objects as two clones.

Walk through an example

The object the reference builds in its own demo covers stages 2 to 4 at once: o = {"a": 1, "n": {"x": 2}} with o["self"] = o and o["p"] and o["q"] both set to one shared = {"s": 1}.

Complexity

Reference: O(V + E) time, where V is the number of distinct containers and E the number of references inside them, because each container is cloned once and each reference followed once; O(V) space for seen plus O(depth) stack. Plain recursion: time proportional to the structure unfolded into a tree, which is exponential when objects are shared and never ends on a cycle.

Edge cases to test

• A self-cycle, o = {"a": 1}; o["self"] = o: c["self"] is c must be True. A visited set that returns the original instead gives c["self"] is o, a clone that points back into the source.
• A cycle through a list, xs = [1]; xs.append(xs): lists go through the same seen map, so c[1] is c and c is not xs.
• Equal but distinct objects, {"p": {"s": 1}, "q": {"s": 1}}: c["p"] is c["q"] must stay False. The map is keyed by identity, id(value) in Python and the object itself in a JavaScript Map; a key built from the contents would merge them.
• Sharing that compounds: 20 levels where each holds two references to the next. The map clones 21 dicts; plain recursion makes 2,097,151.
• Deep nesting with no cycle at all, 2,000 dicts each inside the next: the recursive reference still raises RecursionError, because Python’s default limit is 1,000 frames. Only an explicit stack removes the depth limit.
• Primitives and None: deep_clone(7), deep_clone(None) and deep_clone("s") return the value itself. In TypeScript, typeof null === "object", so the null check has to come before the object branch.

Common mistakes

• Using a plain set of visited objects to stop the recursion, which breaks the cycle but returns the wrong shape — you need the map from original to clone, not a membership test.
• Cloning shared sub-objects twice, so out.a === out.b is false when src.a === src.b was true.
• Recording the clone in the map only after its children are filled: the cycle reaches the original again before the entry exists, and the recursion never ends.
• Forgetting that arrays are objects too, and cloning them into plain objects with numeric keys.
• Treating null as an object and recursing into it — the classic typeof null === "object" trap in JavaScript.

Follow-ups an interviewer asks next

The structure is a million levels deep. Remove the recursion.

Use an explicit stack of (original, clone) pairs. Create each clone, record it in seen, and push the pair; when you pop a pair, fill the clone’s slots, creating, recording and pushing any child that is not yet in seen. The filling order changes but the result does not: every container is still cloned once, and cycles and sharing resolve through the same map.

Support sets, dates and class instances too.

Add a branch per type. Copy a date by value, rebuild a set from cloned members, and for a class instance create an empty instance without running its constructor, record it in seen, then clone its fields. Python’s copy.deepcopy works this way: it keeps a memo keyed by id(), and a class can override the behavior with a __deepcopy__ method.

Why not just call the standard library?

In production, do. Python’s copy.deepcopy uses the same identity map, and JavaScript’s structuredClone preserves cycles and shared references. Neither clones everything: structuredClone throws a DataCloneError on a function and returns a class instance as a plain object with its prototype gone. Building it yourself is how you learn where those limits are.

What is wrong with JSON.parse(JSON.stringify(x))?

It throws a TypeError on a cycle and creates a separate copy of a shared object for every reference, so stages 3 and 4 both fail. It is also lossy: dates become strings, undefined values and functions are dropped from objects, and NaN and Infinity become null. It is a serialization round trip, not a clone.

Where this shows up

Every serializer, state-management library and undo stack meets this. The reason it is a good incremental round is that each stage is a reasonable next sentence from an interviewer, and the third one genuinely breaks the obvious design — so it tests whether you refactor calmly or patch around the symptom. Narrating "a visited set fixes the crash but loses shared identity, so I want a map instead" is the whole signal.

Reference solution

def deep_clone(value, seen=None):
    if seen is None:
        seen = {}

    # primitives and None pass straight through
    if not isinstance(value, (dict, list)):
        return value

    key = id(value)
    if key in seen:              # stage 3 + 4: already cloned this exact object
        return seen[key]

    if isinstance(value, list):
        out = []
        seen[key] = out          # record BEFORE recursing, or a cycle never ends
        for item in value:
            out.append(deep_clone(item, seen))
        return out

    out = {}
    seen[key] = out
    for k, v in value.items():
        out[k] = deep_clone(v, seen)
    return out


o = {"a": 1, "n": {"x": 2}}
o["self"] = o
shared = {"s": 1}
o["p"], o["q"] = shared, shared

c = deep_clone(o)
print(c is not o, c["self"] is c, c["p"] is c["q"], c["n"] is not o["n"])
# -> True True True True

function deepClone(value: any, seen = new Map<any, any>()): any {
  // primitives and null pass straight through (typeof null === "object")
  if (value === null || typeof value !== "object") return value;

  if (seen.has(value)) return seen.get(value);   // stage 3 + 4

  if (Array.isArray(value)) {
    const out: any[] = [];
    seen.set(value, out);                        // record BEFORE recursing
    for (const item of value) out.push(deepClone(item, seen));
    return out;
  }

  const out: any = {};
  seen.set(value, out);
  for (const k of Object.keys(value)) out[k] = deepClone(value[k], seen);
  return out;
}

const o: any = { a: 1, n: { x: 2 } };
o.self = o;
const shared = { s: 1 };
o.p = shared; o.q = shared;

const c = deepClone(o);
console.log(c !== o, c.self === c, c.p === c.q, c.n !== o.n);
// -> true true true true