1161 Maximum Level Sum of a Binary Tree ✅¶

Use List<int>() to track sum on each level

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 1: alt

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.

Example 2:

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

C# Solution¶

using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Medium
{
  public class MaximumLevelSumBinaryTree
  {
    public static int MaxLevelSum(TreeNode root)
    {
      if (root == null) return 0;

      var levels = new List<int>();
      var levelIndex = 0;

      var queue = new Queue<TreeNode>();
      queue.Enqueue(root);

      while (queue.Count > 0)
      {

        var queueCount = queue.Count;

        for (var i = 0; i < queueCount; i++)
        {

          var currentNode = queue.Dequeue();
          if (levels.Count > levelIndex)
          {
            levels[levelIndex] = levels[levelIndex] + currentNode.val;
          }
          else
          {
            levels.Add(currentNode.val);
          }

          if (currentNode.left != null) queue.Enqueue(currentNode.left);
          if (currentNode.right != null) queue.Enqueue(currentNode.right);
        }

        levelIndex++;
      }

      // + 1 since we started with level 0
      return levels.IndexOf(levels.Max()) + 1;
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class MaximumLevelSumBinaryTreeTests
  {
    [Fact]
    public void MaxLevelSumTest1()
    {
      TreeNode l0 = new TreeNode(1);
      l0.left = new TreeNode(7);
      l0.right = new TreeNode(0);
      l0.left.left = new TreeNode(7);
      l0.left.right = new TreeNode(-8);

      Assert.Equal(2, MaximumLevelSumBinaryTree.MaxLevelSum(l0));
    }

    [Fact]
    public void MaxLevelSumTest2()
    {
      TreeNode l0 = new TreeNode(989);
      l0.right = new TreeNode(10250);
      l0.right.left = new TreeNode(98693);
      l0.right.right = new TreeNode(-89388);
      l0.right.right.right = new TreeNode(-32127);

      Assert.Equal(2, MaximumLevelSumBinaryTree.MaxLevelSum(l0));
    }
  }
}