Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Approach 1: BFS
- Add the elements to the queue
- At any given level, calculate the sum of that level and mark the current level
Algorithm:
- Add the node values to the queue starting with the root.
- At a level, calculate the level sum of every level and keep a variable to track the maximum level.
- Repeat it until the queue is empty.
- Return the maximum level.
Code:
class Solution {
public int maxLevelSum(TreeNode root) {
int maxLevel = 1;
int maxSum = Integer.MIN_VALUE;
int level = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
int sum = 0;
for(int i=0; i<size; i++){
TreeNode node = queue.remove();
sum = sum + node.val;
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
if(sum>maxSum){
maxSum = sum;
maxLevel = level;
}
level++;
}
return maxLevel;
}
}
Time Complexity: O(n)
Where n is the number of nodes in the binary tree.
Space Complexity: O(w)
Where w is the maximum width of the binary tree — the maximum number of nodes at any level.
Approach 2 : DFS
- We make use of the arraylist to store the sum of the level at each node which is represented using the index.
- Then we access it by running the loop.
Algorithm:
- We are storing the sum of each level in the arraylist.
- If the
list.size()==level, we add the node value. Else, we get the list value which is the of that level and add the current node value. - We do it for all the left and right subtrees.
- Now, traverse through the list and get the maximum level sum.
Code:
class Solution {
List<Integer> list;
public int maxLevelSum(TreeNode root) {
list = new ArrayList<>();
getLevelSum(root, 0);
int maxLevel = 0;
int maxSum = Integer.MIN_VALUE;
for(int i=0; i<list.size(); i++){
if(list.get(i)>maxSum){
maxLevel = i+1;
maxSum = list.get(i);
}
}
return maxLevel;
}
void getLevelSum(TreeNode root, int level){
if(root==null)
return;
if(list.size()==level){
list.add(root.val);
}
else{
list.set(level, list.get(level)+root.val);
}
getLevelSum(root.left, level+1);
getLevelSum(root.right, level+1);
}
}
Time Complexity: O(n)
Where n is the number of nodes in the tree.
Space Complexity: O(h) for recursion + O(d) for list storage
Where h is the height of the tree and d is the depth (number of levels) of the tree.
Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more
If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7
Top comments (0)