Given a Binary Tree having positive and negative nodes. Find the maximum sum of a level in the given Binary Tree.
Example 1:
Input :               
             4
          /    \
         2     -5
        / \    / \
      -1   3  -2  6
Output: 6
Explanation :
Sum of all nodes of 0'th level is 4
Sum of all nodes of 1'th level is -3
Sum of all nodes of 2'th level is 6
Hence maximum sum is 6
Example 2:
Input :          
            1
          /   \
         2     3
        / \     \
       4   5     8
                / \
               6   7  
Output :  17
Explanation: Maximum sum is at level 2.
Your Task:  
You dont need to read input or print anything. Complete the function maxLevelSum() which takes root node as input parameter and returns the maximum sum of any horizontal level in the given Binary Tree.
Expected Time Complexity: O(N), where N is no of node.
Expected Auxiliary Space: O(W), Where W is the max width of the tree.
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Sorting

Range queries

Starter code: # Your task is to complete this function

# function should return max sum level in the tree

'''

class Node:

    def __init__(self, value):

        self.left = None

        self.data = value

        self.right = None

'''

class Solution:

    def maxLevelSum(self, root):

        # Code here



Solutions:
class Solution:

	def maxLevelSum(self, root):
		d = {}

		def preo(root, l):
			if root == None:
				return root
			try:
				d[l] += root.data
			except:
				d.__setitem__(l, root.data)
			preo(root.left, l + 1)
			preo(root.right, l + 1)
			return root
		preo(root, 0)
		m = -10000000
		try:
			i = 0
			while True:
				m = max(m, d[i])
				i += 1
		except:
			return m


class Solution:

	def maxLevelSum(self, root):
		q = [root]
		mx = -1000000
		while q:
			l = len(q)
			t = 0
			for i in range(l):
				p = q.pop(0)
				t += p.data
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
			mx = max(mx, t)
		return mx


class Solution:

	def maxLevelSum(self, root):
		su = -10 ** 28
		l = [root]
		if root != None:
			su = root.data
		while l:
			r = []
			s = 0
			for i in l:
				if i.left:
					r.append(i.left)
					s += i.left.data
				if i.right:
					r.append(i.right)
					s += i.right.data
			if r == []:
				return su
			if s > su:
				su = s
			l = r
		return su


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		q = deque()
		q.append(root)
		lvl = 0
		ans = -99999999999999999999
		while q:
			n = len(q)
			temp_sum = 0
			for i in range(n):
				temp = q.popleft()
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				temp_sum += temp.data
			ans = max(ans, temp_sum)
		return ans


class Solution:

	def fun(self, root, level, l):
		if root == None:
			return
		if level >= len(l):
			l.append([])
		l[level].append(root.data)
		self.fun(root.left, level + 1, l)
		self.fun(root.right, level + 1, l)

	def maxLevelSum(self, root):
		l = []
		self.fun(root, 0, l)
		if len(l) > 1:
			m = sum(l[0])
		for i in l:
			m = max(m, sum(i))
		return m


def maxlevelsum(root):
	if not root:
		return 0
	queue = [(root, 1)]
	level_sums = {}
	while queue:
		(node, level) = queue.pop(0)
		level_sums[level] = level_sums.get(level, 0) + node.data
		if node.left:
			queue.append((node.left, level + 1))
		if node.right:
			queue.append((node.right, level + 1))
	max_sum = max(level_sums.values())
	return max_sum

class Solution:

	def maxLevelSum(self, root):
		return maxlevelsum(root)


class Solution:

	def maxLevelSum(self, root):
		(de, ans, check) = (deque([None, root]), [], [])
		while de:
			x = de.pop()
			if not x:
				if de:
					de.appendleft(None)
				ans.append(check)
				check = []
			else:
				check.append(x.data)
				if x.left:
					de.appendleft(x.left)
				if x.right:
					de.appendleft(x.right)
		check = [sum(ans[i]) for i in range(len(ans))]
		return max(check)


class Solution:

	def solve(self, root, dic, l):
		if root == None:
			return
		if l not in dic:
			dic[l] = root.data
		else:
			dic[l] += root.data
		if self.ans < dic[l]:
			self.ans = dic[l]
		l += 1
		self.solve(root.left, dic, l)
		self.solve(root.right, dic, l)
		l -= 1

	def maxLevelSum(self, root):
		self.ans = float('-inf')
		dic = {}
		self.solve(root, dic, 0)
		k = dic.values()
		return max(k)


class Solution:

	def maxLevelSum(self, root):
		stack = [root]
		res = -10 ** 10
		while stack:
			depth = len(stack)
			total = 0
			while depth > 0:
				top = stack.pop(0)
				total += top.data
				if top.left:
					stack.append(top.left)
				if top.right:
					stack.append(top.right)
				depth -= 1
			res = max(res, total)
		return res


class Solution:

	def maxLevelSum(self, root):
		q = [root]
		maxi = root.data
		while q:
			s = 0
			l = []
			for i in range(len(q)):
				node = q.pop(0)
				s += node.data
				if node.left:
					l.append(node.left)
				if node.right:
					l.append(node.right)
			maxi = max(maxi, s)
			q = l[:]
		return maxi


class Solution:

	def maxLevelSum(self, root):
		max_sum = -1000000
		qu = []
		qu.append(root)
		while len(qu):
			l = len(qu)
			summ = 0
			while l:
				curr = qu.pop(0)
				summ += curr.data
				if curr.left:
					qu.append(curr.left)
				if curr.right:
					qu.append(curr.right)
				l -= 1
			max_sum = max(max_sum, summ)
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		maxVal = -1000000
		queue = []
		queue.append(root)
		while queue:
			floorMax = 0
			i = len(queue)
			for j in range(i):
				node = queue.pop(0)
				floorMax += node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			maxVal = max(maxVal, floorMax)
		return maxVal


class Solution:

	def maxLevelSum(self, root):
		ans = float('-inf')
		queue = [root]
		while queue:
			level_sum = 0
			for i in range(len(queue)):
				node = queue.pop()
				level_sum += node.data
				if node.left:
					queue.insert(0, node.left)
				if node.right:
					queue.insert(0, node.right)
			ans = max(ans, level_sum)
		return ans


class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return 0
		result = root.data
		q = []
		q.append(root)
		while q != []:
			c = len(q)
			res = 0
			while c != 0:
				c -= 1
				temp = q[0]
				q.pop(0)
				res = res + temp.data
				if temp.left is not None:
					q.append(temp.left)
				if temp.right is not None:
					q.append(temp.right)
			result = max(res, result)
		return result


class Solution:

	def maxLevelSum(self, root):
		q = []
		q.append(root)
		maxi = root.data
		while len(q) != 0:
			n = len(q)
			s = 0
			while n != 0:
				x = q.pop(0)
				s += x.data
				n -= 1
				if x.left != None:
					q.append(x.left)
				if x.right is not None:
					q.append(x.right)
			maxi = max(maxi, s)
		return maxi


class Solution:

	def maxLevelSum(self, root):
		Q = []
		max_ = -900000
		Q.append(root)
		while len(Q) > 0:
			sum_ = 0
			n = len(Q)
			for i in range(n):
				popped = Q.pop(0)
				sum_ += popped.data
				if popped.left:
					Q.append(popped.left)
				if popped.right:
					Q.append(popped.right)
			if sum_ > max_:
				max_ = sum_
		return max_


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		max_summ = root.data
		queue = deque()
		summ = 0
		queue.appendleft(root)
		while queue:
			list_arr = []
			summ = 0
			size = len(queue)
			for i in range(size):
				k = queue.pop()
				if k.left is not None:
					queue.appendleft(k.left)
				if k.right is not None:
					queue.appendleft(k.right)
				list_arr.append(k.data)
			summ = sum(list_arr)
			if summ > max_summ:
				max_summ = summ
		return max_summ


class Solution:

	def maxLevelSum(self, root):
		dir = {}
		level = 0

		def max_level(root, dir, level):
			if not root:
				return
			if dir.get(level):
				dir[level] = dir[level] + root.data
			elif not dir.get(level):
				dir[level] = root.data
			max_level(root.left, dir, level + 1)
			max_level(root.right, dir, level + 1)
		maxx = -10000000000000000000000000000000000000000
		max_level(root, dir, level)
		for i in dir:
			maxx = max(maxx, dir.get(i))
		return maxx


class Solution:

	def maxLevelSum(self, root):
		ans = -100000000000000000000000000
		q = [root]
		while q:
			list = []
			for i in q:
				list.append(i.data)
			ans = max(sum(list), ans)
			for _ in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return ans


class Solution:

	def maxLevelSum(self, root):
		maximum = -9999999

		def bfs(root, maximum):
			if root == None:
				return
			q = [root]
			while q:
				lvl = []
				for i in range(len(q)):
					node = q.pop(0)
					lvl.append(node.data)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				maximum = max(maximum, sum(lvl))
			return maximum
		return bfs(root, maximum)


class Solution:

	def maxLevelSum(self, root):
		res = []
		q = deque()
		if root:
			q.append(root)
		while q:
			val = []
			for i in range(len(q)):
				node = q.popleft()
				val.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			res.append(val)
		maxi = []
		for i in range(len(res)):
			maxi.append(sum(res[i]))
		return max(maxi)


class Solution:

	def maxLevelSum(self, root):
		max_sum = -10000000
		q = []
		q.append(root)
		while len(q):
			l = len(q)
			summ = 0
			while l:
				curr = q.pop(0)
				summ += curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
				l -= 1
			max_sum = max(max_sum, summ)
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		d = {}

		def dfs(root, level):
			if not root:
				return
			if level in d:
				d[level] += root.data
			else:
				d[level] = root.data
			dfs(root.left, level + 1)
			dfs(root.right, level + 1)
		dfs(root, 0)
		return max(d.values())


class Solution:

	def maxLevelSum(self, root):
		if not root:
			return 0
		max_sum = float('-inf')
		q = [root]
		while q:
			level_sum = 0
			size = len(q)
			for i in range(size):
				node = q.pop(0)
				level_sum += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			max_sum = max(max_sum, level_sum)
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		d = deque()
		d.append(root)
		ans = root.data
		while d:
			l = len(d)
			cur = 0
			for i in range(l):
				node = d.popleft()
				cur += node.data
				if node.left:
					d.append(node.left)
				if node.right:
					d.append(node.right)
			ans = max(ans, cur)
		return ans


class Solution:

	def maxLevelSum(self, root):
		levelSum = {}
		currLevel = 0
		queue = [root]
		while queue:
			for i in range(len(queue)):
				curr = queue.pop(0)
				if currLevel in levelSum:
					levelSum[currLevel] += curr.data
				else:
					levelSum[currLevel] = curr.data
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			currLevel += 1
		maxSum = -float('inf')
		for i in range(currLevel):
			maxSum = max(maxSum, levelSum[i])
		return maxSum


class Solution:

	def getT(self, root, dic, lev):
		if not root:
			return
		try:
			ar = dic[lev]
			ar.append(root.data)
			dic[lev] = ar
		except:
			dic[lev] = [root.data]
		self.getT(root.left, dic, lev + 1)
		self.getT(root.right, dic, lev + 1)

	def maxLevelSum(self, root):
		dic = {}
		self.getT(root, dic, 0)
		maxx = -1100000000
		for (i, ar) in dic.items():
			summ = 0
			for e in ar:
				summ += e
			if summ > maxx:
				maxx = summ
		return maxx


class Solution:

	def maxLevelSum(self, root):
		q = []
		q.append(root)
		res = -999999999999999999999999999999999999999999999999999999999999999999999999
		while q:
			s = 0
			for i in range(len(q)):
				node = q.pop(0)
				s += node.data
				q.append(node.left) if node.left else None
				q.append(node.right) if node.right else None
			res = max(res, s)
		return res


class Solution:

	def maxLevelSum(self, root):
		queue = []
		queue.append(root)
		m = -9999999999
		while len(queue) > 0:
			s = 0
			for _ in range(len(queue)):
				temp = queue[0]
				s += temp.data
				queue.pop(0)
				if temp.left != None:
					queue.append(temp.left)
				if temp.right != None:
					queue.append(temp.right)
			m = max(s, m)
		return m


class Solution:

	def maxLevelSum(self, root):
		levelArr = {}
		return self.BFS(root, 0, levelArr)

	def BFS(self, root, level, levelArr):
		if root == None:
			return
		if level in levelArr:
			levelArr[level] += root.data
		else:
			levelArr[level] = root.data
		level += 1
		self.BFS(root.left, level, levelArr)
		self.BFS(root.right, level, levelArr)
		return max(levelArr.values())


class Solution:

	def maxLevelSum(self, root):
		max_sum = root.data
		next_layer = [root.left, root.right]
		while len(next_layer) > 0:
			new_next_layer = []
			sum = 0
			for n in next_layer:
				if n is not None:
					sum += n.data
					if n.left is not None:
						new_next_layer.append(n.left)
					if n.right is not None:
						new_next_layer.append(n.right)
			if sum > max_sum:
				max_sum = sum
			next_layer = new_next_layer
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		if root == None:
			return 0
		q = deque()
		q.append(root)
		m = root.data
		while len(q) > 0:
			l = len(q)
			sum = 0
			while l > 0:
				temp = q.popleft()
				sum += temp.data
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				l = l - 1
			m = max(sum, m)
		return m


class Solution:

	def maxLevelSum(self, root):
		maxsum = -1000000
		if root == None:
			return
		queue = [root]
		next_queue = []
		level = []
		result = []
		while queue:
			for root in queue:
				level.append(root.data)
				if root.left != None:
					next_queue.append(root.left)
				if root.right != None:
					next_queue.append(root.right)
			maxsum = max(maxsum, sum(level))
			level = []
			queue = next_queue
			next_queue = []
		return maxsum


class Solution:

	def maxLevelSum(self, root):
		maxsumi = -1000000
		if root == None:
			return 0
		q = []
		q.append(root)
		while len(q):
			l = len(q)
			sumi = 0
			while l:
				curr = q.pop(0)
				sumi += curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
				l -= 1
			maxsumi = max(maxsumi, sumi)
		return maxsumi


from collections import deque
import sys

class Solution:

	def maxLevelSum(self, root):
		q = deque()
		q.append(root)
		maxans = -sys.maxsize
		while q:
			nc = len(q)
			s = 0
			while nc > 0:
				node = q.popleft()
				s += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				nc -= 1
			maxans = max(s, maxans)
		return maxans


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		q = deque([root])
		ans = -10000000000.0
		while q:
			x = 0
			for i in range(len(q)):
				node = q.popleft()
				x += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			ans = max(ans, x)
		return ans


class Solution:

	def maxLevelSum(self, root):
		ans = []
		if root is None:
			return
		queue = deque([root])
		while queue:
			n = len(queue)
			su = 0
			for i in range(0, n):
				node = queue.popleft()
				su += node.data
				if node.left != None:
					queue.append(node.left)
				if node.right != None:
					queue.append(node.right)
			ans.append(su)
		return max(ans)


class Solution:

	def maxLevelSum(self, root):
		ans = -float('inf')
		q = [root]
		while q:
			s = 0
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				s += node.data
			ans = max(ans, s)
		return ans


class Solution:

	def maxLevelSum(self, root):
		self.s = {}

		def t(root, s):
			if root:
				try:
					self.s[s] += root.data
				except:
					self.s[s] = root.data
				t(root.left, s + 1)
				t(root.right, s + 1)
		t(root, 0)
		return max(self.s.values())


from collections import deque as dq

class Solution:

	def maxLevelSum(self, root):
		s = -float('inf')
		q = dq()
		q.append(root)
		while q:
			m = 0
			for i in range(len(q)):
				a = q.popleft()
				m += a.data
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
			s = max(m, s)
		return s


class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return 0
		maximum = -float('inf')
		queue = [root]
		while queue:
			levelSum = 0
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				levelSum += node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			maximum = max(maximum, levelSum)
		return maximum


class Solution:

	def maxLevelSum(self, root):
		q = [root]
		ans = -99999999999999999999
		while q:
			k = 0
			n = len(q)
			for i in range(n):
				kk = q.pop(0)
				k += kk.data
				if kk.left:
					q.append(kk.left)
				if kk.right:
					q.append(kk.right)
			ans = max(ans, k)
		return ans


class Solution:

	def maxLevelSum(self, root):
		a = []
		tr = root
		mx = root.data
		a.append(tr)
		while 1:
			b = []
			sum = 0
			for i in a:
				if i.left != None:
					b.append(i.left)
				if i.right != None:
					b.append(i.right)
				sum = sum + i.data
			a = b
			mx = max(mx, sum)
			if len(a) == 0:
				return mx


class Solution:

	def maxLevelSum(self, root):
		queue = []
		queue.append(root)
		p = []
		while queue:
			ctr = len(queue)
			s = 0
			while ctr:
				dp = queue.pop(0)
				s += dp.data
				if dp.left:
					queue.append(dp.left)
				if dp.right:
					queue.append(dp.right)
				ctr -= 1
			p.append(s)
		return max(p)


class Solution:

	def maxLevelSum(self, root):
		q = deque()
		q.append(root)
		max_sum = float('-inf')
		while q:
			n = len(q)
			x = 0
			for _ in range(n):
				node = q.popleft()
				x += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if max_sum < x:
				max_sum = x
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		max_sum = -1000000
		qu = []
		qu.append(root)
		while len(qu):
			l = len(qu)
			sum = 0
			while l:
				cur = qu.pop(0)
				sum += cur.data
				if cur.left:
					qu.append(cur.left)
				if cur.right:
					qu.append(cur.right)
				l -= 1
			max_sum = max(max_sum, sum)
		return max_sum


class Solution:

	def maxLevelSum(self, root):

		def helper(root, level, dic):
			if root == None:
				return
			else:
				helper(root.left, level + 1, dic)
				helper(root.right, level + 1, dic)
				if level in dic:
					dic[level] += root.data
				else:
					dic[level] = root.data
			return dic
		dic = helper(root, 1, {})
		ma = dic[1]
		for i in dic:
			if dic[i] > ma:
				ma = dic[i]
		return ma


class Solution:

	def level_sum(self, root):
		if not root:
			return 0
		curr = []
		queue = [root]
		while queue:
			curr_level = 0
			level_size = len(queue)
			for i in range(level_size):
				node = queue.pop(0)
				curr_level += node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			curr.append(curr_level)
		return curr

	def maxLevelSum(self, root):
		return max(self.level_sum(root))


class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return None
		max_sum = root.data
		nodes_to_visit = []
		if root.left is not None:
			nodes_to_visit.append(root.left)
		if root.right is not None:
			nodes_to_visit.append(root.right)
		while nodes_to_visit:
			current_level_nodes = len(nodes_to_visit)
			current_sum = 0
			while current_level_nodes:
				node = nodes_to_visit.pop(0)
				current_sum += node.data
				if node.left is not None:
					nodes_to_visit.append(node.left)
				if node.right is not None:
					nodes_to_visit.append(node.right)
				current_level_nodes -= 1
			if current_sum > max_sum:
				max_sum = current_sum
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		q = []
		temp = root
		q.append(temp)
		maxsum = -9999
		while q:
			l = len(q)
			temp = 0
			sm = 0
			for i in range(l):
				temp = q.pop(0)
				sm += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			maxsum = max(sm, maxsum)
		return maxsum


class Solution:

	def maxLevelSum(self, root):
		res = []

		def helper(node, level):
			if not node:
				return
			while len(res) <= level:
				res.append(0)
			res[level] += node.data
			helper(node.left, level + 1)
			helper(node.right, level + 1)
		helper(root, 0)
		return max(res)


class Solution:

	def maxLevelSum(self, root):
		S = -float('inf')
		Q = deque()
		Q.append(root)
		while Q:
			M = 0
			n = len(Q)
			for i in range(n):
				a = Q.popleft()
				M += a.data
				if a.left:
					Q.append(a.left)
				if a.right:
					Q.append(a.right)
			S = max(M, S)
		return S


class Solution:

	def maxLevelSum(self, root):
		if not root:
			return
		res = {}

		def lvl_sum(root, lvl):
			nonlocal res
			if not root:
				return
			if res.get(lvl):
				res[lvl] += root.data
			else:
				res[lvl] = root.data
			lvl_sum(root.left, lvl + 1)
			lvl_sum(root.right, lvl + 1)
		lvl_sum(root, 0)
		return max(res.values())


class Solution:

	def maxLevelSum(self, root):
		queue = []
		ans = float('-inf')
		queue.append(root)
		while queue:
			curr = 0
			for i in range(0, len(queue)):
				t = queue.pop(0)
				curr += t.data
				if t.left:
					queue.append(t.left)
				if t.right:
					queue.append(t.right)
			ans = max(ans, curr)
		return ans


class Solution:

	def maxLevelSum(self, root):
		q = deque()
		q.append(root)
		arr = []
		l = 0
		while q:
			l = len(q)
			x = 0
			for i in range(l):
				temp = q.popleft()
				y = temp.data
				x = x + y
				if temp.left:
					q.extend([temp.left])
				if temp.right:
					q.extend([temp.right])
			arr.append(x)
		return max(arr)


class Solution:

	def maxLevelSum(self, root):
		q = []
		q.append((0, root))
		d = {}
		while len(q) > 0:
			(lvl, n) = q.pop()
			if lvl in d:
				d[lvl] += n.data
			else:
				d[lvl] = n.data
			if n.left != None:
				q.append((lvl + 1, n.left))
			if n.right != None:
				q.append((lvl + 1, n.right))
		max_val = None
		for (k, v) in d.items():
			if max_val == None:
				max_val = v
			else:
				max_val = max(max_val, v)
		return max_val


from collections import deque as d

class Solution:

	def maxLevelSum(self, root):
		ans = float('-inf')
		q = d()
		q.append(root)
		while q:
			add = 0
			for i in range(len(q)):
				curr = q.popleft()
				add += curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			ans = max(ans, add)
		return ans


import sys

class Solution:

	def maxLevelSum(self, root):
		q = []
		ans = -sys.maxsize - 1
		q.append(root)
		while len(q) > 0:
			s = len(q)
			sum = 0
			for i in range(s):
				curr = q.pop(0)
				sum += curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			if sum > ans:
				ans = sum
		return ans


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		q = deque()
		max_sum = -float('inf')
		q.append(root)
		while q:
			curr_sum = 0
			n = len(q)
			for i in range(n):
				curr = q.popleft()
				curr_sum += curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			max_sum = max(curr_sum, max_sum)
		return max_sum


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		ans = -float('inf')
		if not root:
			return None
		queue = deque()
		queue.append(root)
		while queue:
			count = len(queue)
			curr = 0
			for i in range(0, count):
				node = queue.popleft()
				curr += node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			ans = max(curr, ans)
		return ans


class Solution:

	def tra(self, root, dp, l):
		if root == None:
			return
		dp[l] = dp.get(l, 0) + root.data
		self.tra(root.left, dp, l + 1)
		self.tra(root.right, dp, l + 1)

	def maxLevelSum(self, root):
		dp = dict()
		self.tra(root, dp, 0)
		return max(dp.values())


class Solution:

	def maxLevelSum(self, root):
		nodes = [root]
		max_weight = root.data
		while len(nodes) != 0:
			new_nodes = []
			weight = 0
			for n in nodes:
				weight += n.data
				if n.left is not None:
					new_nodes.append(n.left)
				if n.right is not None:
					new_nodes.append(n.right)
			max_weight = max(max_weight, weight)
			nodes = new_nodes
		return max_weight


class Solution:

	def maxLevelSum(self, root):
		dic = {}

		def traverse(root, level):
			if not root:
				return
			if level in dic:
				dic[level] += root.data
			else:
				dic[level] = root.data
			traverse(root.left, level + 1)
			traverse(root.right, level + 1)
		traverse(root, 0)
		ans = list(dic.values())
		return max(ans)


class Solution:

	def maxLevelSum(self, root):
		q = deque()
		ret = []
		q.append(root)
		while q:
			qlen = len(q)
			level = []
			for i in range(qlen):
				node = q.popleft()
				if node:
					q.append(node.left)
					q.append(node.right)
					level.append(node.data)
			if level:
				ret.append(sum(level))
		return max(ret)


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		trav = deque([root])
		res = -10000000.0
		while trav:
			n = len(trav)
			s = 0
			for i in range(n):
				cur = trav.popleft()
				s += cur.data
				if cur.left:
					trav.append(cur.left)
				if cur.right:
					trav.append(cur.right)
			res = max(res, s)
		return res


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		ans = -pow(2, 32)
		d = deque()
		d.append(root)
		d.append(-1)
		while len(d) != 0:
			temp = 0
			while d[0] != -1:
				cnode = d.popleft()
				temp += cnode.data
				if cnode.left != None:
					d.append(cnode.left)
				if cnode.right != None:
					d.append(cnode.right)
			ans = max(ans, temp)
			if len(d) > 1:
				d.append(-1)
			d.popleft()
		return ans


class Solution:

	def maxLevelSum(self, root):
		q = [root]
		ans = float('-inf')
		while q:
			t = len(q)
			tmp = 0
			while t > 0:
				s = q.pop(0)
				if s.left:
					q.append(s.left)
				if s.right:
					q.append(s.right)
				tmp += s.data
				t -= 1
			ans = max(ans, tmp)
		return ans


class Solution:

	def maxLevelSum(self, root):
		q = deque()
		q.append(root)
		maxm = float('-inf')
		while q:
			l = len(q)
			sum = 0
			for i in range(l):
				ele = q.popleft()
				sum += ele.data
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
			maxm = max(maxm, sum)
		return maxm


class Solution:

	def maxLevelSum(self, root):
		ans = float('-inf')
		l = []
		l.append(root)
		while len(l) > 0:
			count = len(l)
			sum = 0
			while count > 0:
				sum += l[0].data
				node = l.pop(0)
				if node.left != None:
					l.append(node.left)
				if node.right != None:
					l.append(node.right)
				count -= 1
			ans = max(ans, sum)
		return ans


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		queue = deque([root])
		level_sum = 0
		max_sum = root.data
		while queue:
			nodes_in_level = len(queue)
			for i in range(nodes_in_level):
				node = queue.pop()
				level_sum += node.data
				if node.left:
					queue.appendleft(node.left)
				if node.right:
					queue.appendleft(node.right)
			max_sum = max(max_sum, level_sum)
			level_sum = 0
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		q = [root, None]
		(m, s) = (-2147483648, 0)
		while q:
			(s, e) = (0, q.pop(0))
			while e:
				s += e.data
				if e.left:
					q.append(e.left)
				if e.right:
					q.append(e.right)
				e = q.pop(0)
			m = max(m, s)
			if q:
				q.append(None)
		return m


from collections import deque, defaultdict

class Solution:

	def maxLevelSum(self, root):
		mp = defaultdict(int)
		q = deque([(root, 0)])
		while q:
			(node, lvl) = q.popleft()
			mp[lvl] += node.data
			if node.left:
				q.append((node.left, lvl + 1))
			if node.right:
				q.append((node.right, lvl + 1))
		ans = root.data
		for num in mp:
			ans = max(ans, mp[num])
		return ans


import collections

class Solution:

	def maxLevelSum(self, root):
		queue = collections.deque()
		queue.append(root)
		m = root.data
		while queue:
			len_queue = len(queue)
			level_ele = []
			for i in range(len_queue):
				node = queue.popleft()
				if node:
					level_ele.append(node.data)
					queue.append(node.left)
					queue.append(node.right)
			if level_ele:
				m = max(m, sum(level_ele))
		return m


class Solution:

	def maxLevelSum(self, root):
		l = {}
		stack = []
		stack.append([root, 0])
		while stack != []:
			node = stack.pop(0)
			if node[1] not in l:
				l[node[1]] = node[0].data
			else:
				l[node[1]] += node[0].data
			if node[0].left != None:
				stack.append([node[0].left, node[1] + 1])
			if node[0].right != None:
				stack.append([node[0].right, node[1] + 1])
		for i in l:
			if l[i] > l[0]:
				l[0] = l[i]
		return l[0]