<p>Given the <code>root</code> of a binary tree, the level of its root is <code>1</code>, the level of its children is <code>2</code>, and so on.</p>

<p>Return the <strong>smallest</strong> level <code>x</code> such that the sum of all the values of nodes at level <code>x</code> is <strong>maximal</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/03/capture.JPG" style="width: 200px; height: 175px;" />
<pre>
<strong>Input:</strong> root = [1,7,0,7,-8,null,null]
<strong>Output:</strong> 2
<strong>Explanation: </strong>
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [989,null,10250,98693,-89388,null,null,null,-32127]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 10<sup>4</sup>]</code>.</li>
	<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
</ul>

# 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

"""
BFS keeping track of the level
Can use a dict (or array) to store results for each level using level as the key
Take the max at the end

Can forgo the array as well!

Every time we go to a new level, we reset the curLevelSum
At the start of the new level or at the very end of the bfs, we compare the curLevelSum
with the maxLevelSum. If it's creater, our tentative answ is the current level
"""
from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        maxLvlSum = root.val
        curLvlSum = root.val
        answLvl = 1
        
        dq = deque([(root,1)])

        curLvl = 0
        while dq:
            node, lvl = dq.popleft()
            #print(lvl, node.val)
            if lvl > curLvl:
                # Moved to a new level, process the previous level
                if curLvlSum > maxLvlSum:
                    #print(curLvlSum, curLvl)
                    answLvl = curLvl
                    maxLvlSum = curLvlSum
                # Reset level state
                curLvl = lvl
                curLvlSum = 0
            
            curLvlSum += node.val
            for nextNode in [node.left, node.right]:
                if nextNode is None:
                    continue
                dq.append((nextNode, lvl+1))

        # Process the last lavel
        if curLvlSum > maxLvlSum:
            #print(curLvlSum, curLvl)
            answLvl = curLvl
            #maxLvlSum = curLvlSum

        return answLvl
165