---
###### tags: `Leetcode`
---
# Leetcode 1161. Maximum Level Sum of a Binary Tree

[link](https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/)

---

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:


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

#### Constraints:

- The number of nodes in the tree is in the range [1, 104].
- -105 <= Node.val <= 105

---

Level order traversal

We can first create a deque object and add the root node to the deque. Then initializes an empty list to store the sum of values at each level.

Next, we can createn a while loop that continues as long as deque is not empty. Inside the while loop, it first initializes a variable totalVal to 0, which will store the sum of values for the nodes in the current level.

Use the for loop to iterate over all the nodes in the current level of the binary tree. It does this by using the length of the deque as the upper bound for the range function. Inside the loop, the code removes the leftmost node from the deque using the popleft method, and adds the node's value to totalVal. If the node has a left or right child, the code adds these nodes to the deque.

After iterating over all the nodes in the current level, the code appends totalVal to the list. Once the while loop has completed, the code returns the index of the maximum value plus 1.

#### Solution 1

# 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:
        q = collections.deque()
        q.append(root)
        lst = []

        while q:
            totalVal = 0
            for i in range(len(q)):
                node = q.popleft()
                if node:
                    totalVal += node.val
                    q.append(node.left)
                    q.append(node.right)

            lst.append(totalVal)
        
        return lst.index(max(lst[:-1])) + 1   
        

O(T): O(n)
O(S): O(h)