Problem

Given a binary tree, return the level of the tree with minimum sum.

OR

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is minimal.

Opposite of this problem - Maximum Level Sum of a Binary Tree.

Examples

Example 1:

graph TD
	A(1) --- B(7) & C(0)
	B --- D(7) & E("-8")
	
  
1
2
3
4
5
6
7

Input: root = [1,7,0,7,-8,null,null]
Output: 3
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the minimum sum which is level 3.

Solution

Method 1 - Level Order Traversal

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int minLevelSum(TreeNode root) {
        int min = Integer.MAX_VALUE, minLevel = 1;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for (int level = 1; !q.isEmpty(); ++level) {
            int sum = 0;
            int sz = q.size();
            while (sz > 0) {
                TreeNode n = q.poll();
                sum += n.val;
                if (n.left != null) { 
                    q.offer(n.left);
                }
                if (n.right != null) {
                    q.offer(n.right);
                }	            
            }
            if (min > sum) {
                min = sum;
                minLevel = level;
            }
        }
        return minLevel;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int minLevelSum(TreeNode root) {
        int min = Integer.MAX_VALUE, minLevel = 1;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for (int level = 1; !q.isEmpty(); ++level) {
            int sum = 0;
            int sz = q.size();
            while (sz > 0) {
                TreeNode n = q.poll();
                sum += n.val;
                if (n.left != null) { 
                    q.offer(n.left);
                }
                if (n.right != null) {
                    q.offer(n.right);
                }	            
            }
            if (min > sum) {
                min = sum;
                minLevel = level;
            }
        }
        return minLevel;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) (at max n elements will be stored by the queue)