Maximum Level Sum of a Binary Tree

Problem

Approach

Pretty straightforward question, just do a level order traversal and get the sum at each level and return the level which is the maximum.

I initially thought that we needed a deque, but turns out the order does not matter. We can just use an array, creating a new array for each level.

Complexity

• Time: $O(V+E)$
• Space: $O(V)$

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        queue = [root]
        maxLevel, maxSum = 1, root.val
        currLevel = 1
 
        while queue:
            newQueue, currSum = [], 0
            for node in queue:
                currSum += node.val
                if node.left: newQueue.append(node.left)
                if node.right: newQueue.append(node.right)
            if currSum > maxSum: maxLevel, maxSum = currLevel, currSum
            queue = newQueue
            currLevel += 1
 
        return maxLevel