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

Difficulty: interview

Starter 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: TreeNode) -> int:
        

Solutions:
# 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: TreeNode) -> int:
        stack = [root]
        ans = -1000000
        result = 1
        level = 1
        
        while stack:
            curr = 0
            newStack = []
            for x in stack:
                curr += x.val
                if x.left:
                    newStack.append(x.left)
                if x.right: 
                    newStack.append(x.right)
            
            stack = newStack
            
            if curr > ans:
                ans = curr
                result = level
                
            level += 1
            
        return result

# 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: TreeNode) -> int:
        nodes=[[root]]
        for node in nodes:
            tmp=[]
            for n in node:
                if n.left:
                    tmp.append(n.left)
                if n.right:
                    tmp.append(n.right)
            if tmp:
                nodes.append(tmp)
        nodes=[sum([n.val for n in node]) for node in nodes]
        return nodes.index(max(nodes))+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: TreeNode) -> int:
        maxLevel = 1
        maxSum = float(\"-inf\")
        queue = deque()
        queue.append(root)
        level = 1
        
        while queue:
            l = len(queue)
            levelSum = 0
            
            for _ in range(l):
                node = queue.popleft()
                levelSum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            if levelSum > maxSum:
                maxLevel = level
                maxSum = levelSum
            level += 1
        
        return maxLevel

# 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: TreeNode) -> int:
        if root==None:
            return 0
        queue=[root]
        maxval=float(\"-inf\")
        maxinde=0
        level=1
        while(queue):
            n=len(queue)
            su=sum([i.val for i in queue])
            if su>maxval:
                maxval=su
                maxinde=level 
            for i in range(n):
                x=queue.pop(0)
                if x.left:
                    queue.append(x.left)
                if x.right:
                    queue.append(x.right)
            level+=1
        return maxinde
            

# 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: TreeNode) -> int:
        #calculate the sum of nodes at each level
        #store the index of the level with max sum until now
        #if two have same, keep the first one, basically only update if its > nonlocal max
        
        #we can use both dfs and bfs here
        #if we go by bfs, keep calculating sum of level as you add them in the queue
        #tc and sc: O(n) and O(n) for qeuue and traversing
        
        #if we apply dfs
        #keep a sum hash mapping every level to its total sum, keeping track of max depth encountered until now
        #later we need to traverse this map and find the level with max sum
        #TC: O(n), SC: O(height) for both stack and result map, but height can be O(n in case of skewed trees)
        #lets go with dfs
        #we can actually calc max sum and max depth on the go, to prevent iterating hash later - we cant do it, because suppose a level was max until a point, then a really negative vlaue is encountered at that level, still the max would be that level according to our current logic, which is wrong, we should calc max depth only later
        
        if not root:
          return 0
        
        #preorder traversal
        map_depth_sums = collections.defaultdict(int)
        
        #to avoid sorting of list to find
        max_level = 0
        max_sum = float(-inf) #since all sums might be negative, we need to find smallest of them all
        
        #[(5,2)]
        #{1: 1, 2: 10, 3: 10}
        #10, 2
        stack = [(root, 1)]
        
        while(stack):
          curr_node, level = stack.pop()
          map_depth_sums[level] += curr_node.val
            
          if curr_node.right:
            stack.append((curr_node.right, level+1))
          if curr_node.left:
            stack.append((curr_node.left, level + 1))
        
        level = 1
        while(level in map_depth_sums):
          if map_depth_sums[level] > max_sum:
            max_sum = map_depth_sums[level]
            max_level = level
          level += 1
          
        return max_level


# 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: TreeNode) -> int:
        collector = collections.defaultdict(int)
        
        def helper(root, d):
            if not root:
                return
            
            collector[d] += root.val
            
            helper(root.right, d+1)
            helper(root.left, d+1)
            return
        
        helper(root, 0)
        
        print(collector)
        best = 0
        for k, v in list(collector.items()):
            if v > collector[best]:
                best = k
        return best+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: TreeNode) -> int:
        if not root:
            return 0
        
        stack = [root]
        levelsum = 0
        maxlevel = float('-inf')
        maxsum = float('-inf')
        currentlevel = 0
        
        while stack:
            slen = len(stack)
            currentlevel += 1
            while slen > 0:
                node = stack.pop(0)
                levelsum += node.val
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
                slen -=1
            
            if levelsum > maxsum:
                maxlevel = currentlevel
                maxsum = levelsum
            
            levelsum = 0
        
        return maxlevel

# 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: TreeNode) -> int:
        level = 0
        max_level = 0
        max_sum = float('-inf')
        
        q = []
        q.append(root)
        
        while q:
            level +=1
            curr = 0
            for _ in range(len(q)):
                node = q.pop(0)
                curr += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if max_sum < curr:
                max_sum = curr
                max_level = level
        return max_level
                
            
        


# 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: TreeNode) -> int:
        
        sums = []
        
        def addLevels(node, level):
            
            if level > len(sums):
                
                sums.append(0)
            
            sums[level - 1] += node.val
            
            if node.left != None:
                
                addLevels(node.left, level + 1)
            
            if node.right != None:
                
                addLevels(node.right, level + 1)
        
        if(root):
            
            addLevels(root, 1)
            return sums.index(max(sums)) + 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
from collections import deque
from collections import defaultdict 

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        
        queue = deque()
        queue.append((root, 1))
        
        
        level_sums = defaultdict(int)
        
        while (len(queue) > 0):
            node_tuple = queue.popleft()
            curr_node = node_tuple[0]
            curr_level = node_tuple[1]
            level_sums[curr_level] += curr_node.val
            if (curr_node.left != None):
                queue.append((curr_node.left, curr_level + 1))
            if (curr_node.right != None):
                queue.append((curr_node.right, curr_level + 1))
                
        max_sum = root.val
        result_level = 1
        
        for level in list(level_sums.keys()):
            if level_sums[level] > max_sum:
                max_sum = level_sums[level]
                result_level = level 
                
        return result_level
                
        


# 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

from collections import defaultdict
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        #have a rst that saves sum at each level
        rstDict = dict()
        def maxLevelRec(root,level):
            nonlocal rstDict
            if(not root):
                return
            if(level in rstDict):
                rstDict[level]+=root.val
            else:
                rstDict[level] = root.val
            maxLevelRec(root.left,level+1)
            maxLevelRec(root.right,level+1)
        maxLevelRec(root,1)
        maxSum = max(rstDict.values())
        for key in list(rstDict.keys()):
            if(rstDict[key] == maxSum):
                return key


# 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: TreeNode) -> int:
        if not root: return 0
        
        levels = []
        
        queue = [root]
        
        while queue:
            new_queue = []
            
            ttl = 0
            for node in queue:
                ttl += node.val
                if node.left:
                    new_queue.append(node.left)
                if node.right:
                    new_queue.append(node.right)
            levels.append(ttl)
            queue = new_queue
        
        curr_max = -float('inf')
        curr_index = -1
        for i, num in enumerate(levels):
            if num > curr_max:
                curr_index = i
                curr_max = num
        return curr_index+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: TreeNode) -> int:
        memo = {}
        self.maxLevelSumHelper(root, memo, 1)
        maxValue = max(memo.values())
        targetKeys = [k for k in memo if memo[k] == maxValue]
        return min(targetKeys)
    
    def maxLevelSumHelper(self, node, memo, depth):
        if node == None:
            return
        
        if depth in memo:
            memo[depth] += node.val
        else:
            memo[depth] = node.val
        
        self.maxLevelSumHelper(node.left, memo, depth + 1)
        self.maxLevelSumHelper(node.right, memo, depth + 1)
        
        return


# 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: TreeNode) -> int:
        self.max_sum = {}
        
        def sum_tree(node: TreeNode,level):
            
            if not node:
                return
            sum_tree(node.left,level+1)
            sum_tree(node.right,level+1)
            if level in self.max_sum:
                self.max_sum[level] +=  node.val
            else:
                self.max_sum[level] =  node.val
            
        sum_tree(root,1)
        output, max_val = float('inf'), -float('inf')
        for key, val in list(self.max_sum.items()):
            if val > max_val:
                output, max_val = key, val
            elif val == max_val:
                output = min(key, output)
        return output
        
             


# 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 dfs(self,final,root,level):
        if root is None : return
        if len(final)<level+1:
            final.append([])
        final[level].append(root.val)
        self.dfs(final,root.left,level+1)
        self.dfs(final,root.right,level+1)
    def maxLevelSum(self, root: TreeNode) -> int:
        final = []
        self.dfs(final,root,0)
        maxx = max([sum(i) for i in final])
        for i in range(len(final)):
            if sum(final[i])==maxx : 
                return i + 1
        return -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
from collections import defaultdict
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if root is None:
            return None
        
        hashmap={}
        que=[]
        que.append((1,root))
        
        while len(que)>0:
            item=que.pop(0)
            depth=item[0]
            node=item[1]
            if depth not in hashmap:
                hashmap[depth]=0
            hashmap[depth]+=node.val
            
            if node.left is not None:
                que.append((depth+1,node.left))
            if node.right is not None:
                que.append((depth+1,node.right))
        
        sorted_dict=dict(sorted(list(hashmap.items()), key=lambda x: x[1],reverse=True))
        #print('Hashmap : ',sorted_dict)
        return list(sorted_dict.keys())[0]


# 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: TreeNode) -> int:
      if not root: return 
      st=[[root,0]]
      ll=[]
      while st:
        r,l=st.pop(0)
        if l==len(ll) : ll.append([])
        ll[l].append(r.val)
        if r.left: st.append([r.left,l+1])
        if r.right:
          st.append([r.right,l+1])
      #print (ll,l)
      m=-1000
      re=0
      for i in range(l+1):
        n=sum(ll[i])
        if m<n:
          m=n
          re=i
      return re+1
        
      
      
      \"\"\"
        if not root:
          return []
        queue,res=[[root, 0]],[]
        while queue:
          #print (queue[0][0].val)
          node,level = queue.pop(0)
          
          if level == len(res):
            res.append([])
        
          res[level].append(node.val)
          if node.left:
            queue.append((node.left, level + 1))
          if node.right:
            queue.append((node.right, level + 1))
          
        return res[::-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: TreeNode) -> int:
        if root is None:
            return 0

        nodes = [(1, root)]
        maxlevelsum = -float('inf')-1
        maxlevel = 0
        currlevel = 1
        currlevelsum = 0
        while len(nodes) != 0:
            curr = nodes.pop(0)
            if curr[0] == currlevel:
                currlevelsum += curr[1].val
            else:
                if currlevelsum > maxlevelsum:
                    maxlevelsum = currlevelsum
                    maxlevel = currlevel
                currlevel = curr[0]
                currlevelsum = curr[1].val

            if curr[1].left is not None:
                nodes.append((curr[0] + 1, curr[1].left))
            if curr[1].right is not None:
                nodes.append((curr[0] + 1, curr[1].right))
            if len(nodes) == 0:
                if currlevelsum > maxlevelsum:
                    maxlevelsum = currlevelsum
                    maxlevel = currlevel

        return maxlevel

# 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: TreeNode) -> int:
        if not root: return 0
        
        queue = [root]
        maxLevel = level = 1
        maxSum = root.val
        
        while queue:
            nextLevel = []
            s = 0
            for n in queue:
                s += n.val
                if n.left:
                    nextLevel.append(n.left)
                if n.right:
                    nextLevel.append(n.right)
            if s > maxSum:
                maxSum, maxLevel = s, level
            queue = nextLevel
            level += 1
        return maxLevel

# 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: TreeNode) -> int:
        level = 1
        count = 1
        bfs = [(root,level)]
        res = dict()
        while (len(bfs) >0):
            node, lvl = bfs[0]
            bfs.remove((node,lvl))
            if (res.get(lvl) == None):
                res[lvl] = 0
            res[lvl] += node.val
            if (node.left):
                bfs.append((node.left, lvl+1))
            if (node.right):
                bfs.append((node.right, lvl + 1))
        maxs = max(res.values())
        for i in list(res.keys()):
            if (res[i]==maxs):
                return i


from collections import defaultdict
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        levelSum = defaultdict(int)
        curLevel = 0
        q = [root]
        while q:
            q_length = len(q)
            for i in range(q_length):
                cur = q.pop()
                levelSum[curLevel] += cur.val
                if cur.left: q.insert(0, cur.left)
                if cur.right: q.insert(0, cur.right)
                
            curLevel += 1
            
        maxSumm = max(levelSum.values())
        for l in range(len(levelSum)):
            if levelSum[l] == maxSumm: return l+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: TreeNode) -> int:
        queue = [root]
        curLevel = maxLevel = 1
        output = root.val
        
        while queue:
            s, nextLevel = 0, []
            for n in queue:
                if n.left:
                    nextLevel.append(n.left)
                if n.right:
                    nextLevel.append(n.right)
                s += n.val
            if s > output:
                output = s
                maxLevel = curLevel
            curLevel += 1
            queue = nextLevel
        return maxLevel


from collections import deque
# 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: TreeNode) -> int:
        queue = deque([[root, 1]])
        best = -math.inf
        ans = 1
        last = 1
        total = 0

        while queue:
            node = queue.popleft()
            if last != node[1]:
                if total > best:
                    best = total
                    ans = last
                last = node[1]
                total = 0
            
            if not node[0]:
                    continue

            total += node[0].val
            
            lvl = node[1]+1
            queue.append([node[0].left, lvl])
            queue.append([node[0].right, lvl])


        return ans


# 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: TreeNode) -> int:
        curr_level = max_level = 1
        max_sum = float('-inf')
        queue = [root,]
        
        while queue:
            curr_sum = sum([x.val for x in queue])
            if (curr_sum > max_sum):
                max_sum, max_level = curr_sum, curr_level
            queue = [y for x in queue for y in [x.left,x.right] if y]
            curr_level+=1
            
        return max_level

# 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 __init__(self):
        self.sums = []
        self.current_level = 1
    def helper(self, root):
        if root is None:
            return
        if len(self.sums)<self.current_level:
            self.sums.append(root.val)
        else:
            self.sums[self.current_level-1] += root.val
        self.current_level += 1
        self.helper(root.left)
        self.helper(root.right)
        self.current_level -= 1
    def maxLevelSum(self, root: TreeNode) -> int:
        self.helper(root)
        return self.sums.index(max(self.sums))+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: TreeNode) -> int:
        d = {}
        
        def f(root, level):
            if root:
                if level in d:
                    d[level] += root.val
                else:
                    d[level] = root.val
                f(root.left, level+1)
                f(root.right, level+1)
        
        f(root, 1)
        m = max(d.values())
        for k in d:
            if d[k] == m:
                return k

# 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: TreeNode) -> int:
        def check(root, level, d):
            if level not in d:
                d[level] = 0
            d[level] += root.val
            if root.left:
                check(root.left, level+1, d)
            if root.right:
                check(root.right, level+1, d)
            return
        
        d = dict()
        check(root, 1, d)
        rtv = 0
        maxs= -float('inf')
        for k in list(d.keys()):
            if d[k] > maxs:
                maxs = d[k]
                rtv = k
        return rtv


# 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: TreeNode) -> int:
        q=[root]
        curr_level=1
        max_level=1
        max_sum=root.val
        while(len(q)!=0):
            level_nodes=len(q)
            sum_=0
            for i in range(level_nodes):
                root=q[0]
                
                if(root!=None):
                    sum_+=root.val
                if(root.left!=None):
                    q.append(root.left)
                if(root.right!=None):
                    q.append(root.right)
                del q[0]
            
            if(sum_>max_sum):
                max_sum=sum_
                max_level=curr_level
                
            
            curr_level+=1
        return max_level


# 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: TreeNode) -> int:
        def helper(root, level, sums):
            if not root: return
            if level > len(sums):
                sums.append(0)
            sums[level-1] += root.val
            helper(root.left, level+1, sums)
            helper(root.right, level+1, sums)
            
        sums = []
        helper(root, 1, sums)
        m, ix = -float('inf'), -1
        for i in range(len(sums)):
            if sums[i] > m:
                m, ix= sums[i], i
        return ix +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: TreeNode) -> int:
        if root is None:
            return 0
        
        queue=[root]
        res=0
        result=[]
        while len(queue)!=0:
            l=len(queue)
            sum1=0
            for i in range(l):
                item=queue.pop(0)
                sum1+=item.val
                if item.left!=None:
                    queue.append(item.left)
                if item.right!=None:
                    queue.append(item.right)
            result.append(sum1)
        return result.index(max(result))+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: TreeNode) -> int:
        queue = [(root, 1)]
        best = -math.inf
        ans = 1
        last = 1
        total = 0

        while queue:
            node = queue.pop(0)
            if last != node[1]:
                if total > best:
                    best = total
                    ans = last
                last = node[1]
                total = 0
            
            if not node[0]:
                    continue

            total += node[0].val
            
            lvl = node[1]+1
            queue.append((node[0].left, lvl))
            queue.append((node[0].right, lvl))


        return ans


# 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: TreeNode) -> int:
        queue = [(root, 1)]
        l_sum = []
        
        while queue:
            c_node, c_level = queue.pop(0)
            if c_node:
                while len(l_sum) < c_level:
                    l_sum.append(0)

                l_sum[c_level-1]+=c_node.val

                queue.append((c_node.left, c_level+1))
                queue.append((c_node.right, c_level+1))
            
        l_max = None
        max_i = 0
        for i in range(len(l_sum)):
            if l_max is None or l_max < l_sum[i]:
                l_max = l_sum[i]
                max_i = i
                
        return max_i+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: TreeNode) -> int:
        curr = [root]
        currLevel = 0
        res = 0
        resSum = float(\"-inf\")

        while curr:
            currSum = 0
            currLevel+=1
            nexx = []
            for n in curr:
                currSum += n.val
                if n.left:
                    nexx.append(n.left)
                if n.right:
                    nexx.append(n.right)
            if resSum < currSum:
                res = currLevel
                resSum = currSum
            curr = nexx
        
        return res

# 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: TreeNode) -> int:
        max_sum = float('-inf')
        level = 0
        max_level = 0
        queue = []
        
        if not root:
            return 0
        
        queue.append(root)
        
        while len(queue) > 0:
            size = len(queue)
            level_sum = 0
            level += 1
            
            for i in range(size):
                node = queue.pop(0)
                level_sum += node.val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if max_sum < level_sum:
                max_sum = level_sum
                max_level = level
        
        return max_level

# 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: TreeNode) -> int:
        dic = collections.defaultdict(int)
        
        def dfs(node, level):
            if not node:
                return
            else:
                dic[level] += node.val
            dfs(node.left, level+1)
            dfs(node.right, level+1)
            
        dfs(root,1)
        
        res = 1
        Max = float('-inf')
        for level,value in list(dic.items()):
            if value>Max:
                Max = value
                res = level
        return res


# 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: TreeNode) -> int:
        res = []
        level = 0
        def dfs(root, res, level):
            if root == None:
                return
            if level >= len(res):
                res.append(0)
            res[level] += root.val
            level += 1
            dfs(root.left, res, level)
            dfs(root.right, res, level)
        dfs(root, res, level)
        return (res.index(max(res))+1)


class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        
        vals={}
        current=[root]
        vals[1]=root.val
        max1=0
        level=0
        cl=1
        
        while len(current):
            nodes=current
            children=[]
            sum1=0
            for node in nodes:
                
                if node.left:
                    children.append(node.left)
                    sum1+=node.left.val
                if node.right:
                    children.append(node.right)
                    sum1+=node.right.val
            
            vals[cl+1]=sum1
            if sum1>=max1:
                level=cl+1
                max1=sum1
            
            if len(children)>0:
                current=children
                cl+=1
            
            else:
                break
        
        
            
        return level


# 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 ht(self, root):
        if (root == None):
            return 0
        return 1 + max(self.ht(root.left), self.ht(root.right))
    
    
    def Sum(self, root, SA, level):
        if (root != None):
            print (level)
            SA[level] += root.val
            if (root.left != None):
                self.Sum(root.left, SA, level + 1)
            if (root.right != None):
                self.Sum(root.right, SA, level + 1)
                
    def maxLevelSum(self, root: TreeNode) -> int:
        SA = [0]*self.ht(root)
        self.Sum(root, SA, 0)
        return SA.index(max(SA)) + 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: TreeNode) -> int:
        if not root:
            return 0
        queue = collections.deque([root])
        maximum = root.val
        maximum_level = 1
        cnt = 1
        while(queue):
            summation = 0
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                summation += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if summation > maximum:
                maximum = summation
                maximum_level = cnt
            cnt += 1
        return maximum_level

# 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 find(self,root,d,s,h):
        if(root==None):
            return None
        if h not in list(d.keys()):
            d[h] = root.val
        else:
            d[h] = d[h]+root.val
        self.find(root.left,d,s,h+1)
        self.find(root.right,d,s,h+1)
        
        
    def maxLevelSum(self, root: TreeNode) -> int:
        d = dict()
        s=[0]
        self.find(root,d,s,1)
        return max(d,key=d.get)
        


# 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
from collections import deque

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        mx = root.val
        mxlvl = 1
        if root.right is None and root.left is None:
            return 1
        
        clvl = 2
        s = 0
        
        q = deque()
        q.append((root.right, 2))
        q.append((root.left, 2))
        while q:
            n, lvl = q.popleft()
            if n is None:
                continue
            if lvl == clvl:
                s += n.val
                print((s, clvl))
            else:
                if s > mx:
                    mx = s
                    mxlvl = clvl
                    mx = s
                s = n.val
                clvl = lvl
            q.append((n.left, lvl + 1))
            q.append((n.right, lvl + 1))
        if s > mx:
            mx = s
            mxlvl = clvl
        return mxlvl


# 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
from collections import deque

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        mx = root.val
        mxlvl = 1
        if root.right is None and root.left is None:
            return 1
        
        clvl = 2
        s = 0
        
        q = deque()
        q.append((root.right, 2))
        q.append((root.left, 2))
        while q:
            n, lvl = q.popleft()
            if n is None:
                continue
            if lvl == clvl:
                s += n.val
                print(s, clvl)
            else:
                if s > mx:
                    print(f\"UP: {s=} {mx=} {mxlvl=} {lvl=}\")
                    mx = s
                    mxlvl = clvl
                    print(f\"UP: {s=} {mx=} {mxlvl=} {lvl=}\")
                    mx = s
                s = n.val
                clvl = lvl
            q.append((n.left, lvl + 1))
            q.append((n.right, lvl + 1))
        if s > mx:
            mx = s
            mxlvl = clvl
        return mxlvl
        

# 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: TreeNode) -> int:
        if not root:
            return 
        
        from collections import deque
        import sys
        queue = deque([root])
        global_value = -sys.maxsize
        level = 0
        while queue:
            level += 1
            level_value = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                level_value += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            if level_value > global_value:
                global_value = level_value
                global_level = level
        
        return global_level
                
            
        


# 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: TreeNode) -> int:
        level = 1
        
        def recurse(root, level):
            if root:
                recurse(root.left, level+1)
                print(level)
                print(\"val\", root.val)
                level_store[level] +=root.val
                recurse(root.right, level+1)
        
        level_store = collections.defaultdict(int)
        recurse(root, level)
        
        print(level_store)
        max_so_far = float(\"-inf\")
        index = -1
        for key, value in level_store.items():
            if value>max_so_far:
                max_so_far = value
                index = key
            elif value==max_so_far:
                index=min(key, index)
                
        return index
                
                


# 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: TreeNode) -> int:
        if root is None:
            return 0
        if not root.left and not root.right:
            return root.val
        arr = [[root.val]]
        def helper(n,l):
            if not n:
                return
            if len(arr) < l+1:
                arr.append([])
            arr[l].append(n.val)
            helper(n.left,l+1)
            helper(n.right,l+1)
        
        helper(root.left,1)
        helper(root.right,1)
        print(arr)
        res = -2**32 + 1 
        ans = 1
        for j,i in enumerate(arr):
            if sum(i) > res:
                res = sum(i)
                ans = j+1
        return ans


# 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: TreeNode) -> int:
        res = self.helper(root)
        return res.index(max(res)) + 1
        
    def helper(self, root):
        if not root:
            return []
        res, left, right = [root.val], self.helper(root.left), self.helper(root.right)
        l = min(len(left), len(right))
        for i in range(l):
            res.append(left[i] + right[i])
        res = res + left[l:] + right[l:]
        return res

# 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: TreeNode) -> int:
        if not root:
            return 0
        
        queue = [root]
        maxSum = root.val
        res = 1
        level = 0
        
        while queue:
            size = len(queue)
            currSum = 0
            level += 1
            
            for _ in range(size):
                node = queue.pop(0)
                currSum += node.val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if maxSum < currSum:
                maxSum = currSum
                res = level
                
        return res 

# 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: TreeNode) -> int:
        levelMapping = {}
        queue = []
        queue.append([root, 1])
        while queue:
            s = queue.pop(0)
            
            if s[0] == None:
                continue
            
            if s[1] in levelMapping:
                if levelMapping[s[1]]:
                    levelMapping[s[1]] += s[0].val
            else:
                levelMapping[s[1]] = s[0].val
            queue.append([s[0].left, s[1]+1])
            queue.append([s[0].right, s[1]+1])
        maximum = -999999999999999999999
        maximum_level = 0
        print(levelMapping)
        for key in levelMapping:
            if levelMapping[key] and maximum < levelMapping[key]:
                maximum = levelMapping[key]
                maximum_level = key
        return maximum_level
            
        


# 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 __init__(self):
        self.sols = {}
        
    def nodes_at_level(self, root, level, target, nodes):
        if root == None:
            return nodes
        
        if level == target:
            nodes.append(root)
            return nodes
        
        self.nodes_at_level(root.left, level+1, target, nodes)
        self.nodes_at_level(root.right, level+1, target, nodes)
        
        return nodes
    def sum_at_level(self, root, level, target):
        if root == None:
            return 0
        
        
        if level == target:
            return root.val
        
        result = sum((self.sum_at_level(root.left, level +1, target), self.sum_at_level(root.right, level+1, target)))
        
        return result
        
    def level_count(self, root):
        if root == None:
            return 0
        
        if root in self.sols:
            return self.sols[root]
        
        result = 1 + max(self.level_count(root.left), self.level_count(root.right))
        
        self.sols[root] = result
        
        return result
    
    def all_children(self, nodes):
        for node in nodes:
            if node.left != None:
                yield node.left
            if node.right != None:
                yield node.right
    
    def maxLevelSum(self, root: TreeNode) -> int:
        levels = [[root]]#{1: [root]}
        
        do_more = True
        cur = 1
        
        max_index = 0    
        max_val = sum([x.val for x in levels[-1]])
        while do_more:
            nodes = levels[-1]
            new_nodes = tuple(self.all_children(nodes))
            levels.append(new_nodes)
            do_more = len(new_nodes) > 0
            
            cur_val = sum([x.val for x in new_nodes])
            if cur_val > max_val:
                max_val = cur_val
                max_index = cur
                
            cur += 1
        
        for i, level in enumerate(levels):
            level_sum = sum([x.val for x in level])
            if level_sum > max_val:
                max_index = i
                max_val = level_sum
        #for i, l in enumerate(levels):
        #    print(i, list(map(lambda x: x.val, l)))
        #print([random.randint(-100000,100000) for _ in range(10000)])
        return max_index+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
import collections
import heapq
import sys
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        lSums = dict()
        q = collections.deque()
        
        level = 0
        q.append(root)
        while q:
            size = len(q)
            level += 1
            levelSum = 0
            for i in range(size):
                node = q.popleft()
                levelSum += node.val
                if node.left != None:
                    q.append(node.left)
                if node.right != None:
                    q.append(node.right)
        
            lSums[level] = levelSum
            
        minLevel = sys.maxsize
        maxSum = -sys.maxsize
        
        for level in lSums:
            localSum = lSums[level]
            #print(\"level %d sum %d maxSum %d minLel %d\" % (level, localSum, maxSum, minLevel))
            if maxSum < localSum :
                minLevel = level
                maxSum = localSum
                
        return minLevel
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        
        from collections import defaultdict
        
        self.sums = defaultdict(int)
        
        def helper(node, level):
            if node is not None:
                self.sums[level] += node.val
                helper(node.right, level+1)
                helper(node.left, level+1)
        
        helper(root,1)
        
        return sorted(list(self.sums.items()),key=lambda t:t[1], reverse=True)[0][0]
            


# 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


from collections import defaultdict


class Solution:
    
    
    def max_level_sum_rec(self, cur, cur_level):
        result = defaultdict(int)
        if cur:
            result[cur_level] += cur.val
        if cur.left:
            left_result = self.max_level_sum_rec(cur.left, cur_level+1)
            for k,v in left_result.items():
                result[k] += v
        if cur.right:
            right_result = self.max_level_sum_rec(cur.right, cur_level+1)
            for k,v in right_result.items():
                result[k] += v
        
        return result
        
    
    def maxLevelSum(self, root: TreeNode) -> int:
        result = self.max_level_sum_rec(root, 1)
        print(result)
        return sorted(
            result.items(),
            key=lambda t: (t[1], -t[0]),
            reverse=True
        )[0][0]

# 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: TreeNode) -> int:
        level = 0
        max_level = 0
        max_sum = float('-inf')
        
        q = collections.deque()
        q.append(root)
        
        while q:
            level += 1
            curr_sum = 0
            
            for _ in range(len(q)):
                node = q.popleft()
                
                curr_sum += node.val
                
                if node.left:
                    q.append(node.left)
                    
                if node.right:
                    q.append(node.right)
                    
            if max_sum < curr_sum:
                max_sum = curr_sum
                max_level = level
            
        return max_level
        

        
        
        
        


# 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: TreeNode) -> int:
        
        queue = [root]
        max_sum = float('-inf')
        max_level = 0
        level = 0
        while len(queue) > 0:
            level_length = len(queue)
            level_sum = 0
            for i in range(level_length):
                node = queue.pop(0)
                level_sum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if max_sum < level_sum:
                max_sum = level_sum
                max_level = level + 1
            level += 1

        return max_level


# 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: TreeNode) -> int:
        level = 0
        max_level = 0
        max_sum = float('-inf')
        
        q = collections.deque()
        q.append(root)
        
        while q:
            level += 1
            curr_sum = 0
            
            for _ in range(len(q)):
                node = q.popleft()
                
                curr_sum += node.val
                
                if node.left:
                    q.append(node.left)
                    
                if node.right:
                    q.append(node.right)
                    
            if max_sum < curr_sum:
                max_sum = curr_sum
                max_level = level
                
        return max_level

# 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: TreeNode) -> int:
        queue = deque()
        result = 1
        queue.append((root, 1))
        maxsum = - sys.maxsize
        while queue:
            size = len(queue)
            level_sum = 0
            for i in range(size):
                node, level = queue.popleft()
                level_sum += node.val
                if node.left:
                    queue.append((node.left, level+1))
                if node.right:
                    queue.append((node.right, level+1))
            if level_sum > maxsum:
                maxsum = level_sum
                result = level
        return result

# 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: TreeNode) -> int:
        
        #bfs
        
        q = [root]
        sums = []
        while len(q)>0 :
            s = len(q)
            tmp = 0
            for i in range(s) :
                n = q.pop(0)
                tmp += n.val
                if n.left :
                    q.append(n.left)
                if n.right :
                    q.append(n.right)
                    
            sums.append(tmp)
        
        level_sums = sorted(zip(range(len(sums)), sums), key=lambda x : (-x[1], x[0]))
        return level_sums[0][0]+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: TreeNode) -> int:
        if root == None:
            return 0
        traversing = [(1, root)]
        level_sum = dict()
        while traversing:
            cur = traversing.pop()
            level_sum[cur[0]] = level_sum.get(cur[0], 0) + cur[1].val
            if cur[1].left:
                traversing.append((cur[0] + 1, cur[1].left))
            if cur[1].right:
                traversing.append((cur[0] + 1, cur[1].right))
        return max((v, k) for k, v in level_sum.items())[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 levelSumHelper(self, node, level, sums):
        if node is None:
            return sums
        if(len(sums)==level):
            sums.append(node.val)
        else:
            sums[level]+=node.val
        sums = self.levelSumHelper(node.left, level+1, sums)
        sums = self.levelSumHelper(node.right, level+1, sums)
        return sums
    def maxLevelSum(self, root: TreeNode) -> int:
        sums = self.levelSumHelper(root, 0, [])
        #print(sums)
        m = sums[0]
        ret = 0
        for i, s in enumerate(sums):
            #print(i,s)
            #print(m, ret)
            if s>m:
                m = s
                ret = i
        return ret+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: TreeNode) -> int:
        
        self.l = [0]*100000
        self.max = float(\"-inf\")
        self.ans = 0
        
        def ankit(root,level):
            
            if(root is not None):
                ankit(root.left,level+1)
                self.l[level]+= root.val
                ankit(root.right,level+1)
                
        ankit(root,1)
        return self.l.index(max(self.l))
                    
                
            
        

# 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: TreeNode) -> int:
        
        #bfs
        
        q = [root]
        sums = []
        while len(q)>0 :
            s = len(q)
            tmp = 0
            for i in range(s) :
                n = q.pop(0)
                tmp += n.val
                if n.left :
                    q.append(n.left)
                if n.right :
                    q.append(n.right)
                    
            sums.append(tmp)
        
        print(sums)
        level_sums = sorted(zip(range(len(sums)), sums), key=lambda x : (-x[1], x[0]))
        return level_sums[0][0]+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: TreeNode) -> int:
        res = self.helper(root)
        return res.index(max(res)) + 1
        
    def helper(self, root):
        if not root:
            return []
        left, right = self.helper(root.left), self.helper(root.right)
        l = min(len(left), len(right))
        res = [root.val] + [sum(p) for p in zip(left, right)] + left[l:] + right[l:]
        return res

# 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: TreeNode) -> int:
        res = self.helper(root)
        return res.index(max(res)) + 1
        
    def helper(self, root):
        if not root:
            return []
        left, right = self.helper(root.left), self.helper(root.right)
        l = min(len(left), len(right))
        return [root.val] + [sum(p) for p in zip(left, right)] + left[l:] + right[l:]


# 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: TreeNode) -> int:
        max_level = -1
        max_sum = -float('inf')

        lv = 1
        lv_nodes = [root]
        while lv_nodes:
            
            if max_sum < sum([n.val for n in lv_nodes]):
                max_level = lv
                max_sum = sum([n.val for n in lv_nodes])
            lv += 1
            new_nodes = []
            for n in lv_nodes:
                if n.left:
                    new_nodes.append(n.left)
                if n.right:
                    new_nodes.append(n.right)
            lv_nodes = new_nodes
        return max_level



# 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

\"\"\"
Approach: Level order traversal (BFS)
- maintain a max_level_sum 
\"\"\"


class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        max_level, level, ans = -float('inf'), 0, 0
        q = collections.deque()
        q.append(root)

        while q:
            level += 1
            level_sum = 0
            for _ in range(len(q)):
                node = q.popleft()
                level_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if max_level < level_sum:
                max_level, ans = level_sum, level        
        return ans

# 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 ht(self, root):
        if (root == None):
            return 0
        return 1 + max(self.ht(root.left), self.ht(root.right))
    
    
    def Sum(self, root, SA, level):
        if (root != None):
            print (level)
            SA[level] += root.val
            if (root.left != None):
                self.Sum(root.left, SA, level + 1)
            if (root.right != None):
                self.Sum(root.right, SA, level + 1)
                
    def maxLevelSum(self, root: TreeNode) -> int:
        SA = [0]*self.ht(root)
        print(\"het \" + str(self.ht(root)))
        self.Sum(root, SA, 0)
        print (SA)
        return SA.index(max(SA)) + 1
            
            
        



class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        
        levels={}
        vals={}
        current=[root]
        levels[root]=1
        vals[1]=root.val
        max1=0
        level=0
        cl=1
        
        while len(current):
            nodes=current
            children=[]
            sum1=0
            for node in nodes:
                
                if node.left:
                    children.append(node.left)
                    sum1+=node.left.val
                if node.right:
                    children.append(node.right)
                    sum1+=node.right.val
            
            vals[cl+1]=sum1
            if sum1>=max1:
                level=cl+1
                max1=sum1
            
            if len(children)>0:
                current=children
                cl+=1
            
            else:
                break
        
        
            
        return level


# 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 __init__(self):
        self.q = collections.deque()
        self.sums = collections.defaultdict()
        
    def bfs(self, root, visited):
        self.q.append(root)
        idx = 1
        
        while self.q:
            level = len(self.q)
            self.sums[idx] = 0
            while level:
                p = self.q.popleft()
                
                if p is None or p in visited:
                    level -= 1
                    continue
                
                self.sums[idx] += p.val
                
                self.q.append(p.left)
                self.q.append(p.right)
                
                level -= 1
                
            idx += 1
        
    def maxLevelSum(self, root: TreeNode) -> int:
        visited = []
        self.bfs(root, visited)
        max_sum = level = 0
        
        for key, value in self.sums.items():
            if value > max_sum:
                max_sum = value
                level = key
        
        return level

# 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: TreeNode) -> int:
        if not root:
            return 0
        q = deque([(root, 1)])
        res = defaultdict(int)
        while q:
            n, l = q.popleft()
            res[l] += n.val
            if n.left:
                q.append((n.left, l+1))
            if n.right:
                q.append((n.right, l+1))
        argmax = 1
        vmax = root.val
        for k, v in list(res.items()):
            if v > vmax:
                argmax = k
                vmax = v
        return argmax
            
            
            
            


# 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: TreeNode) -> int:
        max, level, maxLevel = -float('inf'), 0, 0
        q = collections.deque()
        q.append(root)
        while q:
            level += 1
            sum = 0
            for _ in range(len(q)):
                node = q.popleft()
                sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if max < sum:
                max, maxLevel = sum, level        
        return maxLevel

# 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: TreeNode) -> int:
        def get_level_sums(root: TreeNode, level : int, level_sums : dict):
            if not root:
                return
            if level not in list(level_sums.keys()):
                level_sums[level] = root.val
            else:
                level_sums[level] += root.val
            get_level_sums(root.left, level + 1, level_sums)
            get_level_sums(root.right, level + 1, level_sums)
            
        if not root:
            return 0
        level_sums = {}
        get_level_sums(root, 1, level_sums)
        print (level_sums)
        max_key = 0
        max_value = min(level_sums.values())
        for k in list(level_sums.keys()):
            if level_sums[k] > max_value:
                max_key = k
                max_value = level_sums[k]
        return max_key
                
        
        


from collections import defaultdict
# 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: TreeNode) -> int:
        
        bfs = defaultdict(list)
        
        def traverse(head, n):
            if head is None:
                return
            bfs[n].append(head.val)
            traverse(head.left, n+1)
            traverse(head.right, n+1)
        
        traverse(root, 1)
        
        s=-9999
        l=0
        for i in bfs:
            bfs[i]=sum(bfs[i])
            if bfs[i]>s:
                s=bfs[i]
                l=i
        return l

# 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: TreeNode) -> int:
        stack = [root]
        record = {
            0: root.val
        }
        length = 0
        while len(stack) > 0:
            tmp = []
            val = 0
            length += 1
            for s in stack:
                if s.left:
                    tmp.append(s.left)
                    val += s.left.val
                if s.right:
                    tmp.append(s.right)
                    val += s.right.val
            record[length] = val
            stack = tmp[:]
        max_val = max(list(record.values()))
        for i in range(length):
            if record[i] == max_val:
                return i+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: TreeNode) -> int:
        
        level_sums = [[root.val]]
        
        q = [root]
        
        while q:
            temp = []
            for _ in range(len(q)):
                
                node = q.pop(0)
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                    
                temp.append(node.val)
            
            level_sums.append(temp)
            
        sums = [sum(l) for l in level_sums]
        
        return sums.index(max(sums))
                
            
        


# 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: TreeNode) -> int:
        maxVal = root.val
        ans = level = 1
        stack = [root]
        while True:
            nextStack = []
            level += 1
            sumVal = 0
            for item in stack:
                if item.left:
                    sumVal += item.left.val
                    nextStack.append(item.left)
                if item.right:
                    sumVal += item.right.val
                    nextStack.append(item.right)
            #print(sumVal, level)
            if nextStack:
                stack = nextStack
                if sumVal > maxVal:
                    maxVal = sumVal
                    ans = level
            else:
                break           
            
        return ans
                    
                    
                
        


# 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 __init__(self):
        self.sols = {}
        
    def nodes_at_level(self, root, level, target, nodes):
        if root == None:
            return nodes
        
        if level == target:
            nodes.append(root)
            return nodes
        
        self.nodes_at_level(root.left, level+1, target, nodes)
        self.nodes_at_level(root.right, level+1, target, nodes)
        
        return nodes
    def sum_at_level(self, root, level, target):
        if root == None:
            return 0
        
        
        if level == target:
            return root.val
        
        result = sum((self.sum_at_level(root.left, level +1, target), self.sum_at_level(root.right, level+1, target)))
        
        return result
        
    def level_count(self, root):
        if root == None:
            return 0
        
        if root in self.sols:
            return self.sols[root]
        
        result = 1 + max(self.level_count(root.left), self.level_count(root.right))
        
        self.sols[root] = result
        
        return result
    
    def all_children(self, nodes):
        for node in nodes:
            if node.left != None:
                yield node.left
            if node.right != None:
                yield node.right
    
    def maxLevelSum(self, root: TreeNode) -> int:
        levels = {1: [root]}
        
        do_more = True
        cur = 1
        while do_more:
            nodes = levels[cur]
            cur += 1
            new_nodes = list(self.all_children(nodes))
            levels[cur] = new_nodes
            
            do_more = len(new_nodes) > 0
        
        max_index = 1    
        max_val = sum([x.val for x in levels[max_index]])
        
        for key in levels:
            level_sum = sum([x.val for x in levels[key]])
            if level_sum > max_val:
                max_index = key
                max_val = level_sum
        
        #for key in levels:
        #    print(key, list(map(lambda x: x.val, levels[key])))
        
        return max_index


# 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
import queue
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        q = collections.deque()
        q.append(root)
        maxlevel, level, max = 0, 0, -float('inf')
        while q:
            total = 0
            for _ in range(len(q)):
                node = q.popleft()
                total += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
            if total > max:
                max, maxlevel = total, level
        return maxlevel

from collections import defaultdict
# 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

def rec(root, d, lvl):
    d[lvl]+=root.val
    if root.left:
        rec(root.left, d, lvl+1)
    if root.right:
        rec(root.right, d, lvl+1)

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        d = defaultdict(int)
        rec(root,d,1)
        ans = 1
        for i in d:
            if d[i] > d[ans]:
                ans = i
                
                
        return ans

# 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:
    import collections
    def maxLevelSum(self, root: TreeNode) -> int:
#         bfs to do level traversal and calculate sum, update level if sum is larger
        levelSum = float('-inf')
        res = 0
        queue = collections.deque()
        queue.append((1, root))
        while len(queue) != 0:
            curr_sum = 0
            for _ in range(len(queue)):
                currl, curr = queue.popleft()
                curr_sum += curr.val
                if curr.left:
                    queue.append((currl + 1, curr.left))
                if curr.right:
                    queue.append((currl + 1, curr.right))
            if curr_sum > levelSum:
                res = currl
                levelSum = curr_sum
        return res

# 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: TreeNode) -> int:
        
        queue = deque()
        queue.append(root)
        
        bfs = []
        
        level_sum = 0
        level_nodes = 1
        
        sum_of_levels = []
        
        while queue:
            node = queue.popleft()
            bfs.append(node)
            level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            
            if node.right:
                queue.append(node.right)
            
            level_nodes -= 1
            if level_nodes == 0:
                sum_of_levels.append(level_sum)
                level_sum = 0
                level_nodes = len(queue)
        
        return sum_of_levels.index(max(sum_of_levels)) + 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: TreeNode) -> int:
        def get_size(node):
            if node is None: return 0
            return max(get_size(node.left), get_size(node.right)) + 1
        
        levels = [0] * get_size(root)
        def split(node, level):
            nonlocal levels
            if node is None: return
            levels[level] += node.val
            split(node.left, level + 1)
            split(node.right, level + 1)
        
        split(root, 0)
        return levels.index(max(levels)) + 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: TreeNode) -> int:
        sums = collections.defaultdict(int)
        visited = []
        
        def dfs(root, level):
            if root:
                sums[level] += root.val
                visited.append(root)

                dfs(root.right, level + 1)
                dfs(root.left, level + 1)
        
        dfs(root, 1)
        return max(sums, key=sums.get)

# 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: TreeNode) -> int:
        if not root:
            return 0
        import collections
        queue = collections.deque([root])
        maxx = root.val
        ans = 0
        level = 1
        while queue:
            summ = 0
            for i in range(len(queue)):
                n = queue.popleft()
                if not n:
                    continue
                summ += n.val
                queue.append(n.left)
                queue.append(n.right)
            if summ > maxx:
                ans = level
                maxx = summ
            level += 1
        return ans

# 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: TreeNode) -> int:
        if not root:
            return None
        
        bfs_queue = [root]
        current_sum = 0
        max_level = 0
        level = 0
        
        while True:
            temp = []
            level += 1
            row_sum = 0
            
            while bfs_queue:
                popped = bfs_queue.pop()
                row_sum += popped.val
                
                if popped.left:
                    temp.append(popped.left)
                    
                if popped.right:
                    temp.append(popped.right)
                    
                    
            if not temp:
                if row_sum > current_sum:
                    max_level = level
                    current_sum = row_sum
                break
            
            else:
                if row_sum > current_sum:
                    max_level = level
                    current_sum = row_sum
                bfs_queue = temp
                
        
        return max_level
                


# 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: TreeNode) -> int:
        
        row = [root]
        max_sum = root.val
        rv = row_count = 1
        
        while any(row): 
            new_row = []
            row_sum = 0
            
            for node in row: 
                for child in (node.left, node.right):
                    if child: 
                        new_row.append(child)
                        row_sum += child.val
            
            if new_row: 
                row_count += 1 
                
            if row_sum > max_sum: 
                max_sum = row_sum 
                rv = row_count 
                
            #max_sum = max(max_sum, row_sum)
            row = new_row
        
        return rv
                    
            


# 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 Node:
    def __init__(self, treeNode, level):
        self.treeNode = treeNode
        self.level = level

from collections import deque
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        queue = deque([Node(root, 1)])
        level = 1
        total = 0
        totalMax = 0
        ans = 1
        while queue:
            cur = queue.popleft()
            if cur.level != level:
                if total > totalMax:
                    totalMax = total
                    ans = level
                level = cur.level
                total = 0
                
            total += cur.treeNode.val
            if cur.treeNode.left:
                queue.append(Node(cur.treeNode.left, cur.level + 1))
            if cur.treeNode.right:
                queue.append(Node(cur.treeNode.right, cur.level + 1))
        
        return ans


# 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: TreeNode) -> int:
        
        store = {}
        
        def helper(node, level):
            if node:
                helper(node.left,level+1)
                helper(node.right,level+1)
                
                if level in store:
                    store[level].append(node.val)
                else:
                    store[level] = [node.val]
                    
                return node
            
        helper(root,1)
        
        for i in list(store.keys()):
            store[i] = sum(store[i])
            
        mx = sorted(list(store.items()), key=lambda x: (x[1]))
        return(mx[-1][0])
            
        


# 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: TreeNode) -> int:
        lvl = 1
        sums = [[root.val, 1]]
        
        # apply bfs
        queue = [root]
        tmp = []
        lvl += 1
        while queue:
            node = queue.pop(0)
            if node.left is not None:
                tmp.append(node.left)
            if node.right is not None:
                tmp.append(node.right)
                
            if len(queue) == 0:
                res = 0
                for i in tmp:
                    queue.append(i)
                    res += i.val
                    
                if len(queue) != 0:
                    sums.append([res, lvl])
                tmp = []
                lvl += 1
                
        sums.sort(key = lambda x: x[0])
        return sums[-1][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: TreeNode) -> int:
        stack=[[root,1]]
        l=[]
        while stack:
            ele=stack.pop()
            node=ele[0]
            val=ele[1]
            if(node):
                stack.append([node.left,val+1])
                stack.append([node.right,val+1])
                if(len(l)<val):
                    l.append(node.val)
                else:
                    l[val-1]+=node.val
        maxx=max(l)
        for i in range(len(l)):
            if(l[i]==maxx):
                return i+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
import queue
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        def dfs(root, height):
            if not root: return None
            if len(d) == height:
                d.append(root.val)
            else:
                d[height] += root.val
            dfs(root.left, height+1)
            dfs(root.right, height+1)
        
        d = []
        dfs(root, 0)
        return d.index(max(d))+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: TreeNode) -> int:
        sums,ans={},[float(\"inf\"),float(\"-inf\")]
        def traverse(root,lvl):
            if root:
                if lvl not in sums: sums[lvl]=0
                sums[lvl]+=root.val
                traverse(root.left,lvl+1)
                traverse(root.right,lvl+1)
        traverse(root,1)
        return sorted(sums.items(),key=lambda x: (-x[1],x[0]))[0][0]