Flatten a Multilevel Doubly Linked List

1. Define the problem

Flatten a Multilevel Doubly Linked List

Each item in the input list is either a plain value, or an object of the form { val, child }, where child is itself a nested list in the same format — representing a node whose child pointer leads to a whole separate sub-list. Flatten the structure into a single depth-first order: whenever a node has a child, splice that entire child list in immediately after it, before continuing to whatever originally came next. Return the flattened list of values. Use recursion : flattening a node’s child is a smaller version of the very same problem.

Constraints

0 ≤ list length ≤ 1000
a child list may itself contain further nested children

Example

Inputlist = [1, 2, { val: 3, child: [7, 8, 9] }, 4, 5]

Output[1, 2, 3, 7, 8, 9, 4, 5]

Explanation Node 3's child list [7, 8, 9] is spliced in right after it, before the list continues to 4 and 5.

2. Know the words first

In plain terms

Depth-first: Fully finishing a node's child branch before moving on to whatever comes after that node.

3. Visualize the solution

Recurse into each child list, splice it in, then continue

Statusflatten([1, 2, {3, child}, 4, 5])

Copy 1 and 2 straight into the result — no children yet.

What happens in this step

flattenList([1, 2, {val:3,...}, 4, 5])
  item = 1 → plain value, push 1
  item = 2 → plain value, push 2
  result so far: [1, 2]

Neither 1 nor 2 is an object with a child, so both are pushed straight into the result with no recursion.

Step 1 of 6

Steps to visualize

Walk the list from the front, copying plain values straight into the result.
When a node has a child, recurse on that child list first — flattening it is the exact same problem, just smaller.
Splice the flattened child directly after the node, before whatever originally came next.
Continue flattening the rest of the original list after the splice.
An empty list is the base case: it flattens to nothing.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Recurse into each child list, splice it in, then continue

Statusflatten([1, 2, {3, child}, 4, 5])

Copy 1 and 2 straight into the result — no children yet.

What happens in this step

flattenList([1, 2, {val:3,...}, 4, 5])
  item = 1 → plain value, push 1
  item = 2 → plain value, push 2
  result so far: [1, 2]

Neither 1 nor 2 is an object with a child, so both are pushed straight into the result with no recursion.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function flatten(list) {
  function flattenList(items) {
    const result = [];
    for (const item of items) {
      if (item !== null && typeof item === 'object' && 'val' in item) {
        result.push(item.val);
        if (Array.isArray(item.child) && item.child.length > 0) {
          result.push(...flattenList(item.child)); // recursive case
        }
      } else {
        result.push(item); // base case: a plain value needs no recursion
      }
    }
    return result;
  }

  return flattenList(list);
}

Time: O(n)
Space: O(d + n)

6. Test cases

Test cases

Input	Expected	Covers
`list = [1, 2, { val: 3, child: [7, 8, 9] }, 4, 5]`	`[1, 2, 3, 7, 8, 9, 4, 5]`	example from the docstring
`list = []`	`[]`	base case, empty list flattens to nothing
`list = [1, 2, 3]`	`[1, 2, 3]`	a flat list with no children is unchanged
`list = [{ val: 1, child: [10, 11] }, 2, 3]`	`[1, 10, 11, 2, 3]`	the very first node has a child
`list = [1, 2, { val: 3, child: [10, 11] }]`	`[1, 2, 3, 10, 11]`	the last node has a child, nothing to continue with after the splice
`list = [1, { val: 2, child: [{ val: 3, child: [9] }, 4] }, 5]`	`[1, 2, 3, 9, 4, 5]`	a child list that itself contains a child, two recursive calls deep
`list = [{ val: 1, child: [2] }, { val: 3, child: [4] }]`	`[1, 2, 3, 4]`	more than one node in the same list has a child
`list = [{ val: 1, child: [] }]`	`[1]`	an empty child array is treated the same as no child at all

Flatten a Multilevel Doubly Linked List