Maximum Level Sum of a Binary Tree

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

1. Add the elements to the queue
2. At any given level, calculate the sum of that level and mark the current level

Algorithm:

1. Add the node values to the queue starting with the root.
2. At a level, calculate the level sum of every level and keep a variable to track the maximum level.
3. Repeat it until the queue is empty.
4. 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

1. We make use of the arraylist to store the sum of the level at each node which is represented using the index.
2. Then we access it by running the loop.

Algorithm:

1. We are storing the sum of each level in the arraylist.
2. 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.
3. We do it for all the left and right subtrees.
4. 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