Leetcode 1161. Maximum Level Sum of a Binary Tree

Problem Explanation

In a binary tree, the main goal is to determine the level that has the maximum sum of all its node values. The level of the root is 1 and subsequent levels increments by 1.

Example

Suppose our tree is:

1
2
3       1
4     /   \
5    7     0
6   /       \
7  7        -8

We are to find the level with the maximum sum. For this tree, level 1 has sum 1, level 2 has sum 7 and level 3 has sum -1. Thus level 2 has the maximum sum and is the output.

Approach

We'll do a level order traversal using a queue. We initialize a queue with the root node and loop through each level.

At each level we calculate the sum of node values and if that sum is more than current max sum, we update the max sum and note the level. We continue this until we process all nodes in the tree. Finally, the level with max sum is returned.

Solution

Python Solution

1
2python
3# Definition for a binary tree node.
4# class TreeNode:
5#     def __init__(self, x):
6#         self.val = x
7#         self.left = None
8#         self.right = None
9
10from collections import deque
11class Solution:
12    def maxLevelSum(self, root: TreeNode) -> int:
13        # initialize queue with root
14        queue = deque([root])
15        maxSum = root.val
16        maxLevel = 1
17        level = 0        
18        while queue:
19            level += 1
20            levelSum = 0
21            # calculate current level sum
22            for _ in range(len(queue)):
23                node = queue.popleft()
24                levelSum += node.val
25                if node.left:
26                    queue.append(node.left)
27                if node.right:
28                    queue.append(node.right)          
29            # check if current level sum is greater than max sum
30            if levelSum > maxSum:
31                maxSum = levelSum
32                maxLevel = level           
33        return maxLevel

Java Solution

1
2java
3// Definition for a binary tree node.
4// public class TreeNode {
5//     int val;
6//     TreeNode left;
7//     TreeNode right;
8//     TreeNode(int x) { val = x; }
9// }
10
11import java.util.*;
12class Solution {
13    public int maxLevelSum(TreeNode root) {
14        // initiate queue with root
15        Queue<TreeNode> queue = new LinkedList<>();
16        queue.offer(root);
17        int level = 0, maxSum = Integer.MIN_VALUE, maxLevel = -1;
18        while (!queue.isEmpty()) {
19            level++;
20            int levelSum = 0;
21            int sz = queue.size();
22            // calculate current level sum
23            for (int i = 0; i < sz; i++) {
24                TreeNode node = queue.poll();
25                levelSum += node.val;
26                if (node.left != null)
27                    queue.offer(node.left);
28                if (node.right != null)
29                    queue.offer(node.right);
30            }            
31            // check if current level sum is greater than max
32            if (levelSum > maxSum) {
33                maxSum = levelSum;
34                maxLevel = level;
35            }
36        }
37        return maxLevel;
38    }
39}

JavaScript Solution

1
2javascript
3// Definition for a binary tree node.
4// function TreeNode(val, left, right) {
5//     this.val = (val===undefined ? 0 : val)
6//     this.left = (left===undefined ? null : left)
7//     this.right = (right===undefined ? null : right)
8// }
9 
10var maxLevelSum = function(root) {
11    // initialize queue with root
12    let queue = [root];
13    let maxLevel = 1;
14    let maxSum = root.val;
15    let level = 0;
16    
17    while(queue.length !== 0) {
18        let size = queue.length;
19        level +=1;
20        let levelSum = 0;
21        // calculate level sum
22        for(let i = 0; i < size; i++){
23            let node = queue.shift();
24            levelSum += node.val;
25            if(node.left)
26                queue.push(node.left);
27            if(node.right)
28                queue.push(node.right);
29        }
30        
31        // check if current level sum is greater than max sum
32        if(levelSum > maxSum){
33            maxSum = levelSum;
34            maxLevel = level;
35        }
36    }
37    return maxLevel;
38};

C++ Solution

1
2cpp
3// Definition for a binary tree node.
4// struct TreeNode {
5//     int val;
6//     TreeNode *left;
7//     TreeNode *right;
8// };
9
10#include <queue>
11class Solution {
12public:
13    int maxLevelSum(TreeNode* root) {
14        // initiate queue with root
15        queue<TreeNode*> q;
16        q.push(root);
17        int maxSum = root->val;
18        int maxLevel = 1;
19        int level = 0;
20        
21        while (!q.empty()) {
22            level++;
23            int levelSum = 0;
24            int sz = q.size();
25            // calculate level sum
26            for (int i = 0; i < sz; i++) {
27                TreeNode* node = q.front();
28                q.pop();
29                levelSum += node->val;
30                if (node->left != nullptr)
31                    q.push(node->left);
32                if (node->right != nullptr)
33                    q.push(node->right);
34            }
35            
36            // check if current level sum is greater than max sum
37            if (levelSum > maxSum) {
38                maxSum = levelSum;
39                maxLevel = level;
40            }
41        }
42        return maxLevel;
43    }
44};

C# Solution

1
2cs
3/**
4 * Definition for a binary tree node.
5 * public class TreeNode {
6 *     public int val;
7 *     public TreeNode left;
8 *     public TreeNode right;
9 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16
17public class Solution {
18    public int MaxLevelSum(TreeNode root) {
19        // initiate queue with root
20        Queue<TreeNode> queue = new Queue<TreeNode>();
21        queue.Enqueue(root);
22
23        int level = 0;
24        int maxSum = int.MinValue;
25        int maxLevel = -1;
26
27        while (queue.Count > 0) {
28            level++;
29            int levelSum = 0;
30            int count = queue.Count;
31            // calculate level sum 
32            for (int i=0; i<count; i++) {
33                TreeNode node = queue.Dequeue();
34                levelSum += node.val;
35                if (node.left != null)
36                    queue.Enqueue(node.left);
37                if (node.right != null)
38                    queue.Enqueue(node.right);
39            }
40            
41            // check if current level sum is greater than max sum
42            if (levelSum > maxSum) {
43                maxSum = levelSum;
44                maxLevel = level;
45            }
46        }
47        
48        return maxLevel;
49    }
50}

Each solution calculates the level sum for each level and checks if the sum for that level is higher than the previous maximum level sum. If it is, it updates the maximum level sum and the corresponding level. At the end, it returns the level that had the maximum level sum.All these solutions, Python, Java, JavaScript, C++, and C#, have a space complexity of O(N), where N represents the number of nodes in the tree. This accounts for the space used by the queue in a worst-case scenario, where the level with the maximum number of nodes could end up in the queue.

The time complexity for these solutions are also O(N), since each node is processed only once. Every node is put into the queue and removed from the queue once only.

These are optimal solutions for the level order traversal tree problem. However, please note that actual performance might vary depending on the specific characteristics of the trees, number of levels, and specific conditions in your environment. Always make sure to understand the implications of the algorithm for your specific case and test with larger datasets before choosing the most appropriate solution.

Remember to always consider edge cases such as the tree being empty or a tree with only one node. These edge cases would need to be handled appropriately in a production level code.

In conclusion, traversing a binary tree level by level using a queue is a common and very efficient approach to solve this problem. This method can also be used as a reusable part for many other tree related problems, such as returning all nodes in a certain level, or balancing a binary tree. It's beneficial to understand how this works, as it provides an excellent foundation for mastering more complex tree problems.