< Back





1161. Maximum Level Sum of a Binary Tree

The root level is 1, all the following levels increment from that. We're asked to return the level
that has the maximal sum across all its nodes. We conduct BFS, sum the nodes at each level, and
maintain the maximum we've seen so far. We update the level that has the maximum sum and return it.

The solution is as follows:


  class Solution:
      def maxLevelSum(self, root: Optional[TreeNode]) -> int:
          ans = level = 0
          max_sum = float("-inf")
          queue = [root]

          while queue:
              curr_queue, queue = queue, []
              level += 1
              this_sum = 0

              for node in curr_queue:
                  this_sum += node.val

                  if node.left:
                      queue.append(node.left)
                  if node.right:
                      queue.append(node.right)

              if this_sum > max_sum:
                  ans = level
                  max_sum = this_sum

          return ans


_ Time Complexity:

  O(n) - We traverse O(n) nodes of the tree.

_ Space Complexity:

  O(n) - The queue can contain at most O(n) nodes of the tree.