[LeetCode] Maximum Level Sum of a Binary Tree

Problem: Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Example:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Approach: It's a straight forward problem to solve. We will do level order traversal and take the sum of all the elements at each level. We will compare this sum of current level with max level sum if current sum is strictly (need to return minimum level) greater than than maximum sum than we update the max level sum and max level.

That's all!

Implementation in C#:

    public int MaxLevelSum(TreeNode root)

    {

        if (root == null)

        {

            return 0;

        }

        int maxLevel = 0, maxLevelSum = int.MinValue;

        Queue<TreeNode> queue = new Queue<TreeNode>();

        queue.Enqueue(root);

        int currLevel = 1;

        while(queue.Count != 0)

        {

            int size = queue.Count;

            int currLevelSum = 0;

            for (int i = 0; i < size; ++i)

            {

                var node = queue.Dequeue();

                currLevelSum += node.val;

                if (node.left != null)

                {

                    queue.Enqueue(node.left);

                }

                if (node.right != null)

                {

                    queue.Enqueue(node.right);

                }

            }

            if (currLevelSum > maxLevelSum)

            {

                maxLevelSum = currLevelSum;

                maxLevel = currLevel;

            }

            ++currLevel;

        }

        return maxLevel;

    }

Complexity: O(n)