Find the Level of Tree with Minimum Sum - Solution & Explanation

Problem Overview: Given a binary tree, compute the sum of values at each level and return the level index that has the minimum total. Levels are processed from the root downward, so level 1 contains the root, level 2 contains its children, and so on.

Approach 1: Breadth-First Search / Level Order Traversal (O(n) time, O(w) space)

The most direct solution uses Breadth-First Search to process the tree level by level. Push the root into a queue, then repeatedly remove nodes from the queue while adding their children back. For each iteration, measure the current queue size to determine how many nodes belong to the current level, iterate through them, and compute the level sum.

Track two variables while traversing: the current level number and the smallest sum seen so far. After processing all nodes of a level, compare the computed sum with the minimum sum and update the answer if needed. Because every node is visited exactly once and each edge is processed once when adding children to the queue, the total runtime is O(n). The queue stores at most one level of nodes at a time, which requires O(w) space where w is the maximum tree width.

This approach fits naturally with problems involving level-based calculations in a binary tree. You avoid additional bookkeeping since the traversal order already groups nodes by level.

Approach 2: Depth-First Search with Level Tracking (O(n) time, O(h) space)

A second option uses Depth-First Search to accumulate sums per level. During recursion, pass the current depth and maintain an array or hash map where levelSum[depth] stores the total for that level. Each node contributes its value to the corresponding index before recursively exploring its left and right children.

After the traversal finishes, iterate through the stored level sums to find the smallest value and return its level index. The DFS visits each node once, giving O(n) time complexity. The recursion stack requires O(h) space where h is the tree height, plus the storage for level sums.

DFS is useful when you already perform recursive traversals or when the tree is narrow but deep. However, it requires an extra data structure to group nodes by level.

Recommended for interviews: The BFS level-order traversal is the expected solution. It directly mirrors the problem statement: process the tree one level at a time and compute a running sum. Showing the DFS alternative demonstrates deeper understanding, but the BFS implementation is simpler, avoids extra passes, and clearly communicates how level-based tree problems should be handled.