LeetCode 3157 - Find the Level of Tree with Minimum Sum

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree, where every node contains a positive integer value. Our task is to determine which level of the tree has the smallest sum of node values.

A binary tree is organized into levels:

The root node is at level 1
Its children are at level 2
Their children are at level 3
And so on

For every level, we compute the sum of all node values that appear at that depth. After calculating all level sums, we return the level number whose sum is the minimum among all levels.

There is one important detail in the problem statement: if multiple levels have the same minimum sum, we must return the lowest level number among them. Since level numbering starts at 1, this means we keep the earliest level encountered with the minimum sum.

The input size can be as large as 10^5 nodes, which means the solution must be efficient. Any approach that repeatedly traverses large parts of the tree would become too slow. Since we need information grouped by depth, this strongly suggests using either Breadth-First Search (BFS) or Depth-First Search (DFS) with level tracking.

The node values are between 1 and 10^9, so level sums can become very large. We must use integer types that safely support large sums.

Several edge cases are important:

A tree with only one node
A completely skewed tree, where every node has only one child
Multiple levels having the same minimum sum
Very deep trees
Very wide trees

The problem guarantees that the tree contains at least one node, so we never need to handle an empty tree.

Approaches

Brute Force Approach

A naive strategy would be to process each level separately by repeatedly traversing the tree to find nodes belonging to a particular depth.

For example, we could first compute the tree height. Then for every level from 1 to height, we run a DFS traversal that searches for nodes exactly at that depth and sums their values.

This approach is correct because every node at every level is eventually counted. However, it is inefficient because the tree may be traversed many times. In the worst case, a skewed tree has height n, and each DFS traversal visits nearly all nodes. That leads to quadratic time complexity.

With up to 10^5 nodes, an O(n^2) solution is too slow.

Optimal Approach

The key observation is that the tree can be processed level by level in a single traversal.

Breadth-First Search naturally visits nodes in level order. By using a queue, we can process all nodes currently in one level, compute their sum, and then move to the next level.

At each level:

Determine how many nodes belong to the current level
Remove exactly those nodes from the queue
Compute their sum
Add their children to the queue for the next iteration
Update the answer if this level has a smaller sum

This ensures every node is visited exactly once, giving an efficient linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeated DFS traversal for every level
Optimal	O(n)	O(w)	Single BFS traversal, where `w` is maximum tree width

Algorithm Walkthrough

Breadth-First Search by Level

Initialize a queue and place the root node inside it.

The queue is the core data structure for BFS. It allows us to process nodes level by level in the same order they appear in the tree. 2. Initialize tracking variables.

We maintain:

current_level, starting at 1
minimum_sum, initialized to infinity
answer_level, initialized to 1

Start a loop while the queue is not empty.

Each iteration of this loop processes exactly one tree level. 4. Determine the number of nodes in the current level.

The queue already contains all nodes for the current level. Its size tells us exactly how many nodes belong to that level. 5. Compute the level sum.

Remove exactly level_size nodes from the queue:

Add each node’s value to level_sum
Push the node’s children into the queue if they exist

After processing these nodes, the queue will contain only nodes from the next level. 6. Compare the current level sum with the best answer so far.

If level_sum is strictly smaller than minimum_sum, update:

minimum_sum
answer_level

We use a strict comparison instead of <= because ties should keep the earlier level. 7. Increment the level counter.

Move to the next tree level. 8. Continue until the queue becomes empty.

Once all levels are processed, return answer_level.

Why it works

BFS guarantees that nodes are visited level by level. During each iteration, the queue contains exactly the nodes belonging to one depth of the tree. Therefore, the computed level_sum is correct for that level. Since every node is processed once and every level sum is compared against the current minimum, the algorithm correctly identifies the level with the smallest sum.

Python Solution

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def minimumLevel(self, root: Optional[TreeNode]) -> int:
        queue = deque([root])

        current_level = 1
        answer_level = 1
        minimum_sum = float("inf")

        while queue:
            level_size = len(queue)
            level_sum = 0

            for _ in range(level_size):
                node = queue.popleft()
                level_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            if level_sum < minimum_sum:
                minimum_sum = level_sum
                answer_level = current_level

            current_level += 1

        return answer_level

The implementation closely follows the BFS algorithm described earlier.

The deque from Python’s collections module is used because it provides efficient popleft() operations in constant time. A regular list would make front removals expensive.

The queue begins with the root node. During each loop iteration, level_size captures how many nodes belong to the current level. This prevents nodes from deeper levels from being mixed into the current sum.

Inside the inner loop, each node contributes its value to level_sum. Its children are appended to the queue so they can be processed in the next iteration.

After finishing the level, the algorithm checks whether the current sum is smaller than the best sum seen so far. If it is, the answer variables are updated.

Finally, the level counter increases and the process continues until the queue becomes empty.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minimumLevel(root *TreeNode) int {
    queue := []*TreeNode{root}

    currentLevel := 1
    answerLevel := 1
    minimumSum := int64(1<<63 - 1)

    for len(queue) > 0 {
        levelSize := len(queue)
        var levelSum int64 = 0

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            levelSum += int64(node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        if levelSum < minimumSum {
            minimumSum = levelSum
            answerLevel = currentLevel
        }

        currentLevel++
    }

    return answerLevel
}

The Go solution follows the same BFS structure as the Python version.

One important difference is integer handling. Since node values can be as large as 10^9 and there may be 10^5 nodes, level sums can exceed the range of a 32-bit integer. Therefore, the implementation uses int64 for all sum calculations.

Go does not have a built-in deque type like Python, so the queue is implemented using a slice. Nodes are removed from the front using slicing operations.

The solution also uses nil checks before adding child nodes to the queue.

Worked Examples

Example 1

Input:

root = [50,6,2,30,80,7]

Tree structure:

Step-by-step execution

Level	Nodes	Level Sum	Minimum So Far	Answer
1	[50]	50	50	1
2	[6, 2]	8	8	2
3	[30, 80, 7]	117	8	2

Final answer:

Example 2

Input:

root = [36,17,10,null,null,24]

Tree structure:

Step-by-step execution

Level	Nodes	Level Sum	Minimum So Far	Answer
1	[36]	36	36	1
2	[17, 10]	27	27	2
3	[24]	24	24	3

Final answer:

Example 3

Input:

root = [5,null,5,null,5]

Tree structure:

Step-by-step execution

Level	Nodes	Level Sum	Minimum So Far	Answer
1	[5]	5	5	1
2	[5]	5	5	1
3	[5]	5	5	1

The sums are tied, so we keep the earliest level.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(w)	Queue stores at most one tree level at a time

The algorithm performs a standard BFS traversal. Each node enters and leaves the queue exactly once, so the total work is proportional to the number of nodes.

The space usage depends on the maximum width of the tree. In the worst case, the queue may contain all nodes from the widest level simultaneously.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

sol = Solution()

# Example 1
root1 = TreeNode(
    50,
    TreeNode(6, TreeNode(30), TreeNode(80)),
    TreeNode(2, TreeNode(7))
)
assert sol.minimumLevel(root1) == 2  # minimum sum at level 2

# Example 2
root2 = TreeNode(
    36,
    TreeNode(17),
    TreeNode(10, TreeNode(24))
)
assert sol.minimumLevel(root2) == 3  # deepest level has minimum sum

# Example 3
root3 = TreeNode(5, None, TreeNode(5, None, TreeNode(5)))
assert sol.minimumLevel(root3) == 1  # tie should return earliest level

# Single node tree
root4 = TreeNode(42)
assert sol.minimumLevel(root4) == 1  # only one level exists

# Left-skewed tree
root5 = TreeNode(10, TreeNode(3, TreeNode(1)))
assert sol.minimumLevel(root5) == 3  # smallest value at deepest level

# Balanced tree with equal level sums
root6 = TreeNode(
    4,
    TreeNode(2, TreeNode(1), TreeNode(1)),
    TreeNode(2, TreeNode(1), TreeNode(1))
)
assert sol.minimumLevel(root6) == 1  # all sums equal or larger later

# Large values
root7 = TreeNode(
    10**9,
    TreeNode(10**9),
    TreeNode(1)
)
assert sol.minimumLevel(root7) == 1  # root level smallest

# Minimum sum at middle level
root8 = TreeNode(
    20,
    TreeNode(1, TreeNode(50), TreeNode(50)),
    TreeNode(1)
)
assert sol.minimumLevel(root8) == 2  # middle level minimum

print("All tests passed!")

Test	Why
Example 1	Standard balanced tree
Example 2	Minimum sum occurs at deepest level
Example 3	Verifies tie-breaking behavior
Single node tree	Smallest possible input
Left-skewed tree	Tests deep unbalanced tree
Balanced tree with equal sums	Confirms earliest level is returned
Large values	Ensures no overflow issues
Middle-level minimum	Verifies non-root, non-leaf minimum

Edge Cases

Single Node Tree

A tree containing only the root node is the smallest valid input. A buggy implementation might incorrectly initialize variables or fail to process the first level properly. This implementation handles it naturally because the queue initially contains the root, and the BFS loop processes exactly one level before terminating.

Multiple Levels with the Same Minimum Sum

The problem explicitly states that ties should return the lowest level number. A common mistake is using <= when updating the answer, which would incorrectly replace earlier levels with later ones. This implementation uses a strict < comparison, so the first minimum level is preserved.

Highly Skewed Tree

A tree may resemble a linked list, with each node having only one child. Recursive DFS solutions risk stack overflow on very deep trees. The BFS approach avoids recursion entirely and safely handles trees with up to 10^5 nodes.

Very Large Node Values

Since node values can be up to 10^9, a level sum may become extremely large when many nodes exist at the same depth. The Go implementation uses int64 to safely store large sums, preventing integer overflow issues.