Nested List Weight Sum - Solution & Explanation

Problem Overview: You receive a nested list where each element is either an integer or another list. Each integer contributes to the final sum multiplied by its depth in the structure. The task is to traverse the nested structure and compute the weighted sum of all integers.

Approach 1: Depth-First Search (Recursive Traversal) (Time: O(n), Space: O(d))

The most common solution uses recursion with Depth-First Search. Iterate through each element in the current list. If the element is an integer, add value × depth to the result. If it is another list, recursively process that list with depth + 1. Every nested element is visited exactly once, so the time complexity is O(n), where n is the total number of integers and lists. The recursion stack stores at most the current nesting depth, giving O(d) space complexity.

This approach mirrors the structure of the input. The recursive call naturally tracks the depth, which avoids additional data structures. When implementing the logic, the key operation is checking whether an element is an integer or a list and branching accordingly. This method is concise and typically the fastest to write during interviews.

Approach 2: Breadth-First Search (Level Order Traversal) (Time: O(n), Space: O(w))

An alternative uses Breadth-First Search. Instead of diving deep into the structure, process the nested lists level by level using a queue. Start by pushing the initial list into the queue with depth 1. For each item removed from the queue, multiply integers by the current depth and push nested lists back into the queue with depth + 1. Every element is still processed once, keeping time complexity at O(n).

The queue may temporarily store many elements from the same level, so the space complexity becomes O(w), where w is the maximum width of the nested structure. This method is useful when you want explicit control over level processing, similar to level-order traversal in trees.

Both strategies treat the nested list as a hierarchical structure similar to a tree. DFS relies on recursion to track depth automatically, while BFS tracks depth through queue entries.

Recommended for interviews: The recursive DFS solution is what most interviewers expect. It directly reflects the problem’s hierarchical nature and produces clean code with minimal bookkeeping. BFS demonstrates the same understanding using an iterative structure. Showing DFS first proves you understand recursion and nested traversal, which is commonly evaluated in problems involving DFS and nested data structures.