142. Sum a Nested List

Why this mechanism works

There are two structural cases. An integer already is its own contribution. A list delegates each child to the same contract and adds the returned contributions. The recursive shape follows the data rather than a fixed number of nesting levels.

State and boundaries

Each call returns the sum of exactly its supplied subtree. total accumulates completed child results for a list node.

Protocol

1. If the current item is an integer, return it.
2. Otherwise start total at zero.
3. Recursively sum each child and add its result.
4. Return the accumulated total.

Visualization

[1,[2,[3]],4]
 sum = 1 + sum([2,[3]]) + 4
     = 1 + (2 + 3) + 4 = 10

Python implementation

def nested_sum(item):
    if isinstance(item, int):
        return item
    total = 0
    for child in item:
        total += nested_sum(child)
    return total

Worked execution

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

L2 nested_sum: if isinstance(item, int):
item=[1, [2, [...]], 4]

L4 nested_sum: total = 0
item=[1, [2, [...]], 4]; total=0

L5 nested_sum: for child in item:
item=[1, [2, [...]], 4]; total=0; child=1

L2 nested_sum: if isinstance(item, int):
item=1

L6 nested_sum: total += nested_sum(child)
item=[1, [2, [...]], 4]; total=1; child=1

L5 nested_sum: for child in item:
item=[1, [2, [...]], 4]; total=1; child=[2, [3]]

L2 nested_sum: if isinstance(item, int):
item=[2, [3]]

L4 nested_sum: total = 0
item=[2, [3]]; total=0

... 10 intermediate state changes omitted ...

L6 nested_sum: total += nested_sum(child)
item=[1, [2, [...]], 4]; total=6; child=[2, [3]]

L5 nested_sum: for child in item:
item=[1, [2, [...]], 4]; total=6; child=4

L2 nested_sum: if isinstance(item, int):
item=4

L6 nested_sum: total += nested_sum(child)
item=[1, [2, [...]], 4]; total=10; child=4

L2 nested_sum: if isinstance(item, int):
item=[[], [-2, 3]]

L4 nested_sum: total = 0
item=[[], [-2, 3]]; total=0

L5 nested_sum: for child in item:
item=[[], [-2, 3]]; total=0; child=[]

L2 nested_sum: if isinstance(item, int):
item=[]

L4 nested_sum: total = 0
item=[]; total=0

L5 nested_sum: for child in item:
item=[[], [-2, 3]]; total=0; child=[-2, 3]

L2 nested_sum: if isinstance(item, int):
item=[-2, 3]

L4 nested_sum: total = 0
item=[-2, 3]; total=0

... 3 intermediate state changes omitted ...

L5 nested_sum: for child in item:
item=[-2, 3]; total=-2; child=3

L2 nested_sum: if isinstance(item, int):
item=3

L6 nested_sum: total += nested_sum(child)
item=[-2, 3]; total=1; child=3

L6 nested_sum: total += nested_sum(child)
item=[[], [-2, 3]]; total=1; child=[-2, 3]

Why the solution is correct

Integer leaves are correct directly. If every child call returns its own leaf sum, their sum is exactly the parent list's leaf sum because child occurrences partition that structure. Finite acyclic nesting guarantees termination at leaves or empty lists.

Time and space

O(N) time for N visited integer/list nodes and O(d) call-stack space for maximum nesting depth d.

Common mistakes

Summing only the top level ignores nested leaves. Sharing one global subtotal without a clear contract can double-add child results.

Reasoning card

Transfer exercise

Return both the sum and the number of leaves in one recursive result tuple.