143. Flatten a Nested List

Why this mechanism works

The recursive traversal order determines output order. Pass through lists in their existing order and append an integer immediately when reached. One shared output accumulator avoids repeatedly concatenating growing intermediate lists.

State and boundaries

visit(item) appends exactly that item's leaves to output, preserving order. Each call owns traversal control; output is shared append-only state.

Protocol

1. Create an empty output.
2. On an integer append it.
3. On a list recursively visit children from left to right.
4. Return output after visiting the root.

Visualization

[1,[2,[3]],4]
visit leaves: 1 -> 2 -> 3 -> 4
append-only output: [1,2,3,4]

Python implementation

def flatten_nested(item):
    output = []
    def visit(current):
        if isinstance(current, int):
            output.append(current)
        else:
            for child in current:
                visit(child)
    visit(item)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 flatten_nested: output = []
item=[1, [2, [...]], 4]; output=[]

L4 visit: if isinstance(current, int):
current=[1, [2, [...]], 4]; output=[]

L7 visit: for child in current:
current=[1, [2, [...]], 4]; output=[]; child=1

L4 visit: if isinstance(current, int):
current=1; output=[]

L5 visit: output.append(current)
current=1; output=[1]

L8 visit: visit(child)
current=[1, [2, [...]], 4]; output=[1]; child=1

L7 visit: for child in current:
current=[1, [2, [...]], 4]; output=[1]; child=[2, [3]]

L4 visit: if isinstance(current, int):
current=[2, [3]]; output=[1]

... 13 intermediate state changes omitted ...

L4 visit: if isinstance(current, int):
current=4; output=[1, 2, 3]

L5 visit: output.append(current)
current=4; output=[1, 2, 3, 4]

L8 visit: visit(child)
current=[1, [2, [...]], 4]; output=[1, 2, 3, 4]; child=4

L9 flatten_nested: visit(item)
item=[1, [2, [...]], 4]; output=[1, 2, 3, 4]

L2 flatten_nested: output = []
item=[[], []]; output=[]

L4 visit: if isinstance(current, int):
current=[[], []]; output=[]

L7 visit: for child in current:
current=[[], []]; output=[]; child=[]

L4 visit: if isinstance(current, int):
current=[]; output=[]

L4 visit: if isinstance(current, int):
current=[]; output=[]

Why the solution is correct

An integer appends its single correct leaf. A list visits each child in order, and each child appends its own ordered leaves by the call contract. Their concatenation is precisely the list's flattened leaf order.

Time and space

O(N) traversal time, O(L) output space for L integer leaves and O(d) call-stack space.

Common mistakes

Appending a nested list directly leaves the structure unflattened. Returning and repeatedly adding lists can cause avoidable copying.

Reasoning card

Transfer exercise

Implement the traversal with an explicit stack, pushing children in reverse order to preserve left-to-right output.