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

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

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


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


class Solution:

	def maxLevelSum(self, root: TreeNode) -> int:
		if not root:
			return 0
		map_depth_sums = collections.defaultdict(int)
		max_level = 0
		max_sum = float(-inf)
		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


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


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


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


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


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


from collections import defaultdict

class Solution:

	def maxLevelSum(self, root: TreeNode) -> int:
		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


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


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


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


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


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))
		return list(sorted_dict.keys())[0]


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


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


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


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

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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)


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


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


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


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


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


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


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]]
		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
		return max_index + 1


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]
			if maxSum < localSum:
				minLevel = level
				maxSum = localSum
		return minLevel


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]


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]


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


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


class Solution:

	def maxLevelSum(self, root: TreeNode) -> int:
		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


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]


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, [])
		m = sums[0]
		ret = 0
		for (i, s) in enumerate(sums):
			if s > m:
				m = s
				ret = i
		return ret + 1


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


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


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


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


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


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

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


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


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))


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)
			if nextStack:
				stack = nextStack
				if sumVal > maxVal:
					maxVal = sumVal
					ans = level
			else:
				break
		return ans


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

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


class Solution:
	import collections

	def maxLevelSum(self, root: TreeNode) -> int:
		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


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


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


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)


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


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


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
			row = new_row
		return rv


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


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]


class Solution:

	def maxLevelSum(self, root: TreeNode) -> int:
		lvl = 1
		sums = [[root.val, 1]]
		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]


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


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