Implement Deep Flatten (Recursive, Iterative, and Generator)

The problem

Flatten an arbitrarily nested array — [1, [2, [3, [4]]]] → [1, 2, 3, 4] — without using Array.prototype.flat.

This is the friendliest recursion drill in the catalog, which is exactly why interviewers use it: the base solution takes three minutes, leaving time to probe what they actually care about — complexity of your version, converting recursion to iteration, and whether you know the platform already ships the answer (arr.flat(Infinity), ES2019) and what its semantics are.

Solution 1: recursion (start here)

function deepFlatten(arr) {
  const result = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...deepFlatten(item)); // recurse, then splice results in
    } else {
      result.push(item);
    }
  }
  return result;
}
 
deepFlatten([1, [2, [3, [4, [5]]]], 6]); // [1, 2, 3, 4, 5, 6]

One deliberate choice to narrate: push into one result array, don't concat in a reduce. The elegant-looking reduce((acc, v) => acc.concat(...), []) allocates a new array on every element — O(n²) across the run. It's the identical quadratic-spread trap as in series execution, and calling it out unprompted converts a warm-up into a signal.

Also: Array.isArray, not instanceof Array — the check survives cross-realm arrays (the iframe story).

Solution 2: explicit stack (the "no recursion" follow-up)

A 10,000-deep nesting blows the call stack; the fix is owning the stack yourself:

function deepFlattenIterative(arr) {
  const stack = [...arr];
  const result = [];
 
  while (stack.length > 0) {
    const next = stack.pop();
    if (Array.isArray(next)) {
      stack.push(...next);   // unpack one level; children get re-examined
    } else {
      result.push(next);
    }
  }
  return result.reverse();   // LIFO processed us back-to-front
}

The reverse() at the end is the tell that you actually traced the algorithm: pop takes from the tail, so elements land in reverse order. (Alternatives: shift from the front — O(n) per removal, worse — or push results and reverse once, as here: O(n) total.) This recursion→stack conversion is the same move asked in JSON.parse and deep clone follow-ups — one skill, three costumes.

Solution 3: lazy generator (the senior flex)

function* flattenGen(arr) {
  for (const item of arr) {
    if (Array.isArray(item)) {
      yield* flattenGen(item); // delegate — recursion in generator form
    } else {
      yield item;
    }
  }
}
 
[...flattenGen([1, [2, [3]]])];        // [1, 2, 3] — materialize when needed
for (const x of flattenGen(huge)) {    // …or stream without building the array
  if (found(x)) break;                 // early exit does NO work on the rest
}

The generator changes the cost model: nothing materializes until consumed, and early exit skips the untraversed remainder. That's the same lazy-pipeline idea as iterator helpers, and offering it with the sentence "if the consumer might not need everything, flattening lazily is free" is the strongest ending this question has.

Depth control (the standard extension)

function flattenDepth(arr, depth = 1) {
  if (depth < 1) return arr.slice();
  const result = [];
  for (const item of arr) {
    if (Array.isArray(item) && depth >= 1) {
      result.push(...flattenDepth(item, depth - 1));
    } else {
      result.push(item);
    }
  }
  return result;
}
 
flattenDepth([1, [2, [3, [4]]]], 1); // [1, 2, [3, [4]]]  — flat()'s default!
flattenDepth([1, [2, [3, [4]]]], 2); // [1, 2, 3, [4]]

Matching the built-in's contract matters: arr.flat() defaults to depth 1, not Infinity — a spec detail candidates trip on constantly. deepFlatten ≡ flattenDepth(arr, Infinity) ≡ arr.flat(Infinity).

Edge cases interviewers probe

• Empty arrays vanish — [1, [], [2, []]] → [1, 2]; falls out naturally (nothing to iterate), worth stating.
• Sparse arrays — flat removes holes ([1, , 2].flat() → [1, 2]); for...of visits holes as undefined, so your version keeps them as undefined. A named divergence from the built-in — knowing it exists beats accidentally matching it.
• Non-array iterables stay put — strings, Sets, arguments objects are not flattened (Array.isArray gate); flattening strings char-by-char is the classic overreach bug.
• Cycles — an array containing itself recurses forever; flat also has no cycle protection (it's specced on finite structures). If asked, the WeakSet-of-ancestors pattern from deep clone applies.
• Very deep nesting — solution 1 overflows; solutions 2 and 3 (generators still use the call stack for yield* — so really solution 2) is the survivable one. Precision on which alternatives fix the stack is a nice catch: yield* delegation nests stack frames too.

Common mistakes

• The O(n²) concat-in-reduce.
• toString().split(",") "solutions" — destroys types ("1" not 1), breaks on elements containing commas; it's a party trick, not an answer.
• Forgetting reverse() in the pop-based iterative version (or "fixing" order with shift and going quadratic).
• Claiming flat() defaults to full depth.
• instanceof Array without the cross-realm caveat.

Follow-up questions

• "Flatten an object one level? Deep?" — different question (key paths, a.b.c naming policy); recognizing it's not this algorithm — the recursion is similar but the output contract is a design discussion — is the point.
• "Complexity of each version?" — all O(n) in total elements with the push discipline; recursion adds O(depth) stack; generator adds per-yield overhead but enables early exit. Compare, don't hand-wave.
• "Why does flat exist when flatMap exists?" — flatMap is map+flatten(1) fused in one pass — and arr.flatMap(x => x) is a one-level flatten; the fusion idea connects to pipe and lazy pipelines.
• "Flatten a linked structure / tree instead?" — same traversal skeleton, different child accessor — the question generalizes to DFS, which is what it secretly was all along (the virtual DOM serializer is this traversal over DOM nodes).
• "Stream-flatten an async source?" — async generators (for await + yield*) — the natural bridge to async iteration.