Sponsored
Sponsored
The BFS approach is well-suited for problems involving levels of a binary tree. We will use a queue to process the tree level by level, keeping track of the sum of node values at each level. We will maintain a variable to store the maximum sum encountered and the level corresponding to this maximum sum. By processing level by level, we ensure that when we find a new maximum, it is the smallest level with that sum.
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is enqueued and dequeued exactly once.
Space Complexity: O(m), where m is the maximum number of nodes at any level in the tree, due to the queue holding nodes of a single level.
1// Definition for a binary tree node.
2function TreeNode(val) {
3 this.val = val;
4 this.left = this.right = null;
5}
6
7function maxLevelSum(root) {
8 if (!root) return 0;
9 let queue = [root];
10 let maxSum = -Infinity;
11 let level = 0;
12 let maxLevel = 0;
13
14 while (queue.length > 0) {
15 let levelSize = queue.length;
16 let levelSum = 0;
17 level++;
18 for (let i = 0; i < levelSize; i++) {
19 let node = queue.shift();
20 levelSum += node.val;
21 if (node.left) queue.push(node.left);
22 if (node.right) queue.push(node.right);
23 }
24 if (levelSum > maxSum) {
25 maxSum = levelSum;
26 maxLevel = level;
27 }
28 }
29 return maxLevel;
30}
31
32// Example Usage
33let root = new TreeNode(1);
34root.left = new TreeNode(7);
35root.right = new TreeNode(0);
36root.left.left = new TreeNode(7);
37root.left.right = new TreeNode(-8);
38console.log(maxLevelSum(root));
39The JavaScript solution uses an array as a queue to perform BFS traversal of the tree. It calculates the sum for each level, tracks the maximum sum encountered, and updates the level accordingly.
This approach involves using a DFS traversal to explore the tree. We pass the current depth as a parameter to each recursive call and maintain an array or dictionary to track the sum of values at each level. After the traversal, we determine which level has the highest sum. DFS allows us to explore the tree deeply, and since each call carries a depth count, we can easily track levels.
Time Complexity: O(n)
Space Complexity: O(d), where d is the maximum depth of the tree (related to recursion stack depth and level count in the dictionary).
1from collections import defaultdict
2
3# Definition for a binary tree node.
4class TreeNode
The Python solution uses DFS by recursively traversing the tree and tracking the sum of node values at each level using a dictionary. After completing the traversal, it identifies the level with the maximum sum.