Problem

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 maximal.

Opposite of this problem - Level of Binary Tree with minimum sum.

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: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Example 2:

1
2

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Solution

Method 1 - Level Order Traversal

Use BFS to find the sum of each level, then locate the level with largest sum.

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

    public int maxLevelSum(TreeNode root) {
        int max = Integer.MIN_VALUE, maxLevel = 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 (max < sum) {
                max = sum;
                maxLevel = level;
            }
        }
        return maxLevel;
    }

Complexity

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