Maximum Level Sum of a Binary Tree

#programming #java #algorithms #basic

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

DEV Community

Maximum Level Sum of a Binary Tree

Top comments (0)