Nested List

What is this?

A nested list holds plain numbers as well as more lists inside it, nested as deeply as you like — like boxes packed inside other boxes. If you picture it, the whole thing forms a tree: each number is a leaf and each inner list is a branch. To work with it you simply walk down through the layers, keeping track of how deep you currently are.

💡 Fun fact: This box-inside-a-box shape is exactly how the Lisp programming language has represented all data and code since 1958, and it is why formats like JSON can nest arrays inside arrays without limit.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

Core idea: A nested list — integers and lists, nested arbitrarily — is just a tree. Each integer is a leaf, each sub-list is a branch, and "depth" is simply how far down the traversal you are. Aggregating over it is a plain DFS (or level-by-level BFS), with depth carried along.

The reframe

![The nested list [1, [4, [6]]] drawn as a tree: a depth-1 branch holding leaf 1 and a depth-2 branch, which holds leaf 4 and a depth-3 branch holding leaf 6](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/list/nested-list/nested-list-summary-diagram-1.svg)

Once you see the nesting as a tree, the toolkit is the same as any tree problem: DFS carrying the current depth, or BFS processing one level at a time. The only "interface" wrinkle is that each element answers isInteger() (→ getInteger()) or holds getList().

The problem

• Nested List Weight Sum — sum each integer × its depth (top level = 1). DFS: recurse into sub-lists with depth+1, add value*depth at each integer — depth is just the recursion level, nothing to store. BFS: process level by level with a queue, multiplying by the level number. Both O(N) over all elements.

The follow-up (Weight Sum II) flips the weighting to inverse depth (leaves weigh most) — which is exactly why the BFS-by-level view is worth knowing: you can weight by (maxDepth - level + 1) in a second pass.

Key takeaways

• Nested list = tree; depth = traversal level — don't store it, ride it.
• DFS carries depth+1 into each sub-list; each integer contributes value × depth.
• BFS-by-level is the alternative and the key to the inverse-depth follow-up.
• Why interviewers like it: it checks whether you recognize a disguised tree and pick a clean depth-aware traversal — the same skill behind aggregating any nested document/hierarchy.

Problem: Nested List Weight Sum.