1161. Maximum Level Sum of a Binary Tree | LeetCode Using Python

I tackle the LeetCode problem “1161. Maximum Level Sum of a Binary Tree” using Python. The goal is to identify the level in a binary tree where the sum of the node values is the highest. By employing a Breadth-First Search (BFS) strategy, I efficiently traverse the tree level by level, computing the sum for each level and determining which one has the maximum sum. Watch the video above for a step-by-step explanation and see the code implementation below:

# 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:

        #Since we are going level by level - BFS (Breadth First Seach) is the best approach
        #Time complexity is O(n) - every node is visited once
        #space complexity is O(w) - w is width

        #Edge case:
        if root is None:
            return None

        queue = deque([root]) #first in first out data structure

        maximum_level_sum = 0
        maximum_sum = float('-inf')
        current_level = 0

        while queue:
            current_level += 1
            current_level_sum = 0

            level_length = len(queue)
            for _ in range(level_length):
                node = queue.popleft()
                current_level_sum += node.val

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

            if current_level_sum > maximum_sum:
                maximum_sum = current_level_sum
                maximum_level_sum = current_level

        #return the level with the maximum sum(maximum_level_sum)
        return maximum_level_sum