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)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

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):
		q = [root]
		res = 0
		while q:
			l = len(q)
			tmp = 0
			for i in range(l):
				p = q.pop(0)
				tmp += p.data
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
			if res == 0 and tmp < 0:
				res = tmp
			else:
				res = max(res, tmp)
		return res


def slove(root, lvl, d):
	if root is None:
		return
	if lvl not in d:
		d[lvl] = root.data
	else:
		d[lvl] += root.data
	slove(root.left, lvl + 1, d)
	slove(root.right, lvl + 1, d)

class Solution:

	def maxLevelSum(self, root):
		d = {}
		slove(root, 0, d)
		return max(d.values())


class Solution:

	def maxLevelSum(self, root):
		queue = deque()
		queue.append(root)
		max_sum = -9999
		while queue:
			size = len(queue)
			local_sum = 0
			for _ in range(size):
				curr = queue.popleft()
				local_sum += curr.data
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			max_sum = max(max_sum, local_sum)
		return max_sum


class Solution:

	def maxLevelSum(self, root):
		if not root:
			return 0
		queue = [[root]]
		ans = root.data
		while queue:
			level = queue.pop(0)
			temp = []
			for node in level:
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			if temp:
				queue.append(temp)
				ans = max(ans, sum([node.data for node in temp]))
		return ans


import queue

class Solution:

	def maxLevelSum(self, root):
		maxsum = float('-inf')
		if not root:
			return maxsum
		q = queue.Queue()
		q.put(root)
		while q.qsize():
			sum = 0
			for i in range(q.qsize()):
				node = q.get()
				sum += node.data
				if node.left:
					q.put(node.left)
				if node.right:
					q.put(node.right)
			maxsum = max(maxsum, sum)
		return maxsum


class Solution:

	def maxLevelSum(self, root):
		s1 = [root]
		s2 = []
		ans = -12345678
		while s1 != []:
			a = 0
			for i in s1:
				a = a + i.data
			ans = max(ans, a)
			for j in s1:
				if j.left != None:
					s2.append(j.left)
				if j.right != None:
					s2.append(j.right)
			s1 = s2
			s2 = []
		return ans


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		maximum = -100000
		dQ = deque()
		dQ.append(root)
		while dQ:
			calculate = 0
			times = len(dQ)
			for i in range(times):
				holdnode = dQ.popleft()
				calculate += holdnode.data
				if holdnode.left != None:
					dQ.append(holdnode.left)
				if holdnode.right != None:
					dQ.append(holdnode.right)
			maximum = max(maximum, calculate)
		return maximum


class Solution:

	def maxLevelSum(self, root):
		l = [root, 'a']
		max1 = -2 ** 31
		while True:
			w = l.pop(0)
			s = 0
			while w != 'a':
				if w.left != None:
					l.append(w.left)
				if w.right != None:
					l.append(w.right)
				s += w.data
				w = l.pop(0)
			max1 = max(max1, s)
			if l == []:
				return max1
			l.append('a')


class Solution:

	def maxLevelSum(self, root):
		q = []
		level = []
		ans = -10000
		q.append(root)
		while q != [] and root is not None:
			l = []
			for node in q:
				l.append(node.data)
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			s = sum(l)
			ans = max(ans, s)
			q = level
			level = []
		return ans


class Solution:

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

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


import sys
from queue import Queue

class Solution:

	def maxLevelSum(self, root):
		maxSum = -sys.maxsize
		if root is None:
			return 0
		q = Queue()
		q.put(root)
		while not q.empty():
			sum = 0
			l = q.qsize()
			for i in range(l):
				if q.queue[0].left is not None:
					q.put(q.queue[0].left)
				if q.queue[0].right is not None:
					q.put(q.queue[0].right)
				sum += q.get().data
			maxSum = max(sum, maxSum)
		return maxSum


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


class Solution:

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

	def maxLevelSum(self, root):
		res = []
		self.fun(root, 0, res)
		s = sum(res[0])
		for i in res:
			s = max(s, sum(i))
		return s


class Solution:

	def maxLevelSum(self, root):
		levels = self.getLevelOrderNodes(root)
		levelSums = []
		for level in levels:
			levelSums.append(sum(levels[level]))
		return max(levelSums)

	def getLevelOrderNodes(self, root):
		levels = dict()
		self.levelOrder(root, 0, levels)
		return levels

	def levelOrder(self, curr, currHeight, levels):
		if not curr:
			return
		if currHeight not in levels:
			levels[currHeight] = [curr.data]
		else:
			levels[currHeight].append(curr.data)
		self.levelOrder(curr.left, currHeight + 1, levels)
		self.levelOrder(curr.right, currHeight + 1, levels)


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		q = deque()
		level = 0
		q.appendleft(root)
		res = -9999999999
		while q:
			n = len(q)
			level += 1
			total = 0
			while n > 0:
				n -= 1
				node = q.pop()
				total += node.data
				if node.left:
					q.appendleft(node.left)
				if node.right:
					q.appendleft(node.right)
			res = max(res, total)
		return res


class Solution:

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


from collections import deque

class Solution:

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

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


import collections
import sys

class Solution:

	def maxLevelSum(self, root):
		q = collections.deque()
		q.append(root)
		mx = -sys.maxsize
		while q:
			qLen = len(q)
			sm = 0
			for i in range(qLen):
				cur = q.popleft()
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
				sm += cur.data
			mx = max(mx, sm)
		return mx


class Solution:

	def maxLevelSum(self, root):
		l = []
		q = []
		k = [0]
		m = -1
		q.append(root)
		while q:
			z = q.pop(0)
			x = k.pop(0)
			if m != x:
				m = x
				l.append([])
			l[-1].append(z.data)
			if z.left is not None:
				q.append(z.left)
				k.append(x + 1)
			if z.right is not None:
				q.append(z.right)
				k.append(x + 1)
		s = sum(l[0])
		for x in l:
			if s < sum(x):
				s = sum(x)
		return s


class Solution:

	def maxLevelSum(self, root):
		queue = [root]
		max_sum = float('-inf')
		while len(queue):
			n = len(queue)
			temp = 0
			while n > 0:
				node = queue.pop(0)
				temp += node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				n = n - 1
			max_sum = max(max_sum, temp)
		return max_sum


from collections import deque as d

class Solution:

	def maxLevelSum(self, root):
		l = d()
		b = root
		l.appendleft(root)
		l.appendleft(' ')
		r = -10 ** 9
		lp = []
		while l:
			a = l.pop()
			if a == ' ':
				if sum(lp) > r and lp:
					r = sum(lp)
				lp = []
				if l:
					l.appendleft(' ')
			else:
				if a.left:
					l.appendleft(a.left)
					lp.append(a.left.data)
				if a.right:
					l.appendleft(a.right)
					lp.append(a.right.data)
		if root.data > r:
			return root.data
		return r


class Solution:

	def maxLevelSum(self, root):
		ans = -1000000
		queue = [root]
		level = []
		while queue != [] and root is not None:
			l = []
			for node in queue:
				l.append(node.data)
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			s1 = sum(l)
			ans = max(ans, s1)
			queue = level
			level = []
		return ans


class Solution:

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

		def maxlevel(root, dir, level):
			if not root:
				return
			if dir.get(level):
				dir[level] = dir.get(level) + root.data
			else:
				dir[level] = root.data
			maxlevel(root.left, dir, level + 1)
			maxlevel(root.right, dir, level + 1)
		maxx = -1111111
		maxlevel(root, dir, 0)
		for k in dir:
			maxx = max(maxx, dir.get(k))
		return maxx


class Solution:

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


class Solution:

	def maxLevelSum(self, root):
		bfs = []
		if not root:
			return 0
		queue = deque([])
		queue.append(root)
		while queue:
			size = len(queue)
			currsum = 0
			for i in range(size):
				curritem = queue.popleft()
				currsum += curritem.data
				if curritem.left is not None:
					queue.append(curritem.left)
				if curritem.right is not None:
					queue.append(curritem.right)
			bfs.append(currsum)
		return max(bfs)


class Solution:

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


class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return 0
		q = []
		q.append(root)
		ans = root.data
		while len(q) > 0:
			t = []
			temp_ans = 0
			while len(q) != 0:
				x = q.pop(0)
				temp_ans += x.data
				if x.left is not None:
					t.append(x.left)
				if x.right is not None:
					t.append(x.right)
			if temp_ans > ans:
				ans = temp_ans
			q = t
		return ans


class Solution:

	def maxLevelSum(self, root):
		if not root:
			return 0
		q = [root]
		m = root.data
		while q:
			children = []
			vals = []
			while q:
				val = q.pop(0)
				if val.left:
					children.append(val.left)
					vals.append(val.left.data)
				if val.right:
					children.append(val.right)
					vals.append(val.right.data)
			if vals:
				m = max(m, sum(vals))
			q = children
		return m


class Solution:

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


class Solution:

	def maxLevelSum(self, root):
		s = []
		queue = [root]
		while queue != []:
			t = []
			for i in range(len(queue)):
				curr = queue[0]
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
				t.append(curr.data)
				queue.pop(0)
			s.append(sum(t))
		return max(s)


class Solution:

	def maxLevelSum(self, root):

		def height(node):
			if node is None:
				return 0
			else:
				lheight = height(node.left)
				rheight = height(node.right)
				if lheight > rheight:
					return lheight + 1
				else:
					return rheight + 1

		def currlvl(root, lvl):
			if root is None:
				return
			elif lvl == 1:
				res.append(root.data)
			elif lvl > 1:
				currlvl(root.left, lvl - 1)
				currlvl(root.right, lvl - 1)
		res = []
		l = []
		h = height(root)
		for i in range(1, h + 1):
			currlvl(root, i)
			s = sum(res)
			l.append(s)
			res.clear()
		return max(l)


class Solution:

	def maxLevelSum(self, root):
		p = []
		q = []
		g = {}
		p.append(0)
		q.append(root)
		while len(q) > 0:
			a = p.pop(0)
			b = q.pop(0)
			if a not in g:
				g[a] = [b.data]
			else:
				g[a].append(b.data)
			if b.left != None:
				p.append(a + 1)
				q.append(b.left)
			if b.right != None:
				p.append(a + 1)
				q.append(b.right)
		ans = []
		for x in g:
			ans.append(sum(g[x]))
		return max(ans)


class Solution:

	def maxLevelSum(self, root):
		q = []
		maxx = -999999
		q.append(root)
		while q:
			n = len(q)
			ans = 0
			while n > 0:
				p = q.pop(0)
				ans += p.data
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				n -= 1
			if maxx < ans:
				maxx = ans
		return maxx


class Solution:

	def maxLevelSum(self, root):
		if root != None:
			q = deque()
			q.append(root)
			count = 0
			ans = root.data
			while len(q) > 0:
				count = len(q)
				total = 0
				while count > 0:
					num = q.popleft()
					total += num.data
					if not num.left is None:
						q.append(num.left)
					if not num.right is None:
						q.append(num.right)
					count -= 1
				ans = max(ans, total)
			return ans


class Solution:

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


class Solution:

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


class Solution:

	def maxLevelSum(self, root):
		sum_dict = {}
		q = []
		q.append((root, 0))
		while len(q) != 0:
			tt = q.pop(0)
			if tt[1] not in sum_dict:
				sum_dict[tt[1]] = 0
			sum_dict[tt[1]] += tt[0].data
			if tt[0].left != None:
				q.append((tt[0].left, tt[1] + 1))
			if tt[0].right != None:
				q.append((tt[0].right, tt[1] + 1))
		return max(list(sum_dict.values()))


import collections

class Solution:

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


class Solution:

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


r = 0

class Solution:

	def maxLevelSum(self, root):
		global r
		r = -1000000000000000000
		return self.reverseLevelOrder(root)

	def reverseLevelOrder(self, root):
		global r
		A = []
		B = []
		C = []
		D = []
		if root is None:
			return A
		A.append(root)
		while len(A) > 0:
			while len(A) > 0:
				node = A.pop(0)
				B.append(node.data)
				if node.left is not None:
					D.append(node.left)
				if node.right is not None:
					D.append(node.right)
			A.extend(D)
			D = []
			w = sum(B)
			if w > r:
				r = w
			B = []
		return r


class Solution:

	def maxLevelSum(self, root):
		if not root:
			return
		nodes = [root]
		maxSum = float('-inf')
		while nodes:
			l = len(nodes)
			sumEl = 0
			for i in range(l):
				cur = nodes.pop(0)
				sumEl += cur.data
				if cur.left:
					nodes.append(cur.left)
				if cur.right:
					nodes.append(cur.right)
			maxSum = max(maxSum, sumEl)
		return maxSum


class Solution:

	def maxLevelSum(self, root):
		q = []
		q.append(root)
		mini = -1000000000.0
		while len(q):
			count = len(q)
			s = 0
			while count > 0:
				p = q.pop(0)
				s += p.data
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				count -= 1
			if mini < s:
				mini = s
		return mini


class Solution:

	def maxLevelSum(self, root):

		def traversal(root):
			if root == None:
				return None
			hd = 0
			q = [[root, hd]]
			dict1 = dict()
			while q != []:
				node = q.pop(0)
				if node[-1] not in dict1:
					dict1[node[-1]] = node[0].data
				else:
					dict1[node[-1]] += node[0].data
				hd = node[-1]
				if node[0].left:
					q.append([node[0].left, hd + 1])
				if node[0].right:
					q.append([node[0].right, hd + 1])
			return max(dict1.values())
		return traversal(root)


import math

class Solution:

	def maxLevelSum(self, root):
		ans = dict()
		self.rec(root, 1, ans)
		max_sum = -21321321322321
		for (key, val) in ans.items():
			max_sum = max(max_sum, val)
		return max_sum

	def rec(self, root, level, ans):
		if root == None:
			return
		if level not in ans:
			ans[level] = 0
		ans[level] += root.data
		self.rec(root.left, level + 1, ans)
		self.rec(root.right, level + 1, ans)


class Solution:

	def maxLevelSum(self, root):
		d = {}
		st = []
		st.append([root, 1])
		while st:
			(tamp, dep) = st.pop(0)
			if dep in d.keys():
				d[dep] = d[dep] + tamp.data
			else:
				d[dep] = tamp.data
			if tamp.left:
				st.append([tamp.left, dep + 1])
			if tamp.right:
				st.append([tamp.right, dep + 1])
		return max(d.values())


class Solution:

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

		def dfs(node, lvl):
			if lvl == len(sums):
				sums.append(node.data)
			else:
				sums[lvl] += node.data
			if node.left:
				dfs(node.left, lvl + 1)
			if node.right:
				dfs(node.right, lvl + 1)
		dfs(root, 0)
		return max(sums)


class Solution:

	def maxLevelSum(self, root):
		q = []
		q.append(root)
		q.append('$')
		max = root.data
		sum = 0
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					if sum >= max:
						max = sum
					sum = 0
			else:
				if t.left is not None:
					q.append(t.left)
					sum += t.left.data
				if t.right is not None:
					q.append(t.right)
					sum += t.right.data
		return max


from collections import Counter

class Solution:

	def maxLevelSum(self, root):
		c = Counter()
		self.myFunc(root, c, 0)
		return c.most_common()[0][1]

	def myFunc(self, root, c, level):
		if not root:
			return
		level += 1
		c[level] += root.data
		self.myFunc(root.left, c, level)
		self.myFunc(root.right, c, level)
		return


class Solution:

	def __init__(self):
		self.level = {}

	def trav(self, root, l):
		if l in self.level:
			self.level[l].append(root.data)
		else:
			self.level[l] = [root.data]
		if root.left != None:
			self.trav(root.left, l + 1)
		if root.right != None:
			self.trav(root.right, l + 1)

	def maxLevelSum(self, root):
		self.trav(root, 0)
		flag = True
		maxS = 0
		for l in self.level.keys():
			s = sum(self.level[l])
			if flag or maxS < s:
				flag = False
				maxS = s
		return maxS


import collections

class Solution:

	def maxLevelSum(self, root):
		q = collections.deque([root])
		ans = float('-inf')
		while q:
			sz = len(q)
			s = 0
			for _ in range(sz):
				n = q.popleft()
				s += n.data
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
			ans = max(ans, s)
		return ans


class Solution:

	def maxLevelSum(self, root):
		from collections import deque
		queue = deque([root])
		Max = float('-inf')
		while queue:
			f = lvl = 0
			for _ in range(len(queue)):
				node = queue.popleft()
				if node:
					f = 1
					lvl += node.data
					queue.append(node.left)
					queue.append(node.right)
			if f:
				Max = max(Max, lvl)
		return Max


class Solution:

	def maxLevelSum(self, root):
		d = {}
		l = []
		level = 1
		self.helper(root, level, d)
		for i in d:
			l.append(sum(d[i]))
		return max(l)

	def helper(self, root, level, d):
		if root:
			if root == 'N':
				return
			else:
				if level not in d:
					d[level] = [root.data]
				else:
					d[level].append(root.data)
				self.helper(root.left, level + 1, d)
				self.helper(root.right, level + 1, d)


import collections

class Solution:

	def maxLevelSum(self, root):
		q = collections.deque()
		max_sum = root.data
		q.append(root)
		while len(q) > 0:
			levelSum = 0
			n = len(q)
			for i in range(n):
				currNode = q.popleft()
				levelSum += currNode.data
				if currNode.left:
					q.append(currNode.left)
				if currNode.right:
					q.append(currNode.right)
			max_sum = max(max_sum, levelSum)
		return max_sum


from collections import deque

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

class Solution:

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


class Solution:

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

	def helper(self, root, level=0, levels_sum=None):
		if not root:
			return 0
		if not levels_sum:
			levels_sum = []
		if level == len(levels_sum):
			levels_sum.append(0)
		levels_sum[level] += root.data
		self.helper(root.left, level + 1, levels_sum)
		self.helper(root.right, level + 1, levels_sum)
		return levels_sum


class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return 0
		freq = {}
		self.traversal(root, freq, 0)
		maximum = freq[0]
		for level in freq.keys():
			maximum = max(maximum, freq[level])
		return maximum

	def traversal(self, root, freq, level):
		if root is None:
			return
		if level in freq.keys():
			freq[level] += root.data
		else:
			freq[level] = root.data
		self.traversal(root.left, freq, level + 1)
		self.traversal(root.right, freq, level + 1)


class Solution:

	def maxLevelSum(self, root):

		def helper(root, mp, k):
			if root:
				if k in mp:
					mp[k] += root.data
				else:
					mp[k] = root.data
				helper(root.left, mp, k + 1)
				helper(root.right, mp, k + 1)
		mp = {}
		helper(root, mp, 0)
		return max(mp.values())


class Solution:

	def getTree(self, root, arr, d):
		if not root:
			return
		arr.append([root.data, d])
		self.getTree(root.right, arr, d + 1)
		self.getTree(root.left, arr, d + 1)

	def maxLevelSum(self, root):
		arr = []
		self.getTree(root, arr, 0)
		d = arr[len(arr) - 1][1]
		maxx = -1000000000
		for i in range(0, d + 1):
			summ = 0
			for e in arr:
				if i == e[1]:
					summ = summ + e[0]
			if summ > maxx:
				maxx = summ
		return maxx


class Solution:

	def maxLevelSum(self, root):

		def helper(root):
			ans = -99999
			q = deque()
			t = 0
			if not root:
				return ans
			q.append(root)
			while q:
				for i in range(len(q)):
					a = q.popleft()
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t += a.data
				ans = max(ans, t)
				t = 0
			return ans
		if not root:
			return 0
		return helper(root)


class Solution:

	def maxLevelSum(self, root):
		q = []
		maxi = -100000000000
		if root is None:
			return 0
		q.append(root)
		while len(q) > 0:
			nc = len(q)
			level = [0] * nc
			for i in range(nc):
				node = q.pop(0)
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
				level[i] = node.data
			maxi = max(maxi, sum(level))
		return maxi


class Solution:

	def maxLevelSum(self, root):

		def helper(root):
			ans = -9999999
			q = []
			t = 0
			if not root:
				return x
			q.append(root)
			while q:
				for i in range(len(q)):
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t += a.data
				ans = max(t, ans)
				t = 0
			return ans
		return helper(root)


class Solution:

	def maxLevelSum(self, root):

		def helper(x):
			q = []
			t = []
			ans = -9999
			q.append(x)
			while q:
				l = len(q)
				for i in range(l):
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t.append(a.data)
				ans = max(ans, sum(t))
				t = []
			return ans
		a = helper(root)
		return a


class Solution:

	def maxLevelSum(self, root):
		maxlevel = -float('inf')
		q = [root]
		while q:
			temp = []
			tsum = 0
			for i in q:
				tsum += i.data
				if i.left:
					temp.append(i.left)
				if i.right:
					temp.append(i.right)
			maxlevel = max(maxlevel, tsum)
			q = temp
		return maxlevel


import collections
from collections import deque

class Solution:

	def maxLevelSum(self, root):
		res = float('-inf')
		q = collections.deque()
		q.append(root)
		while q:
			ql = len(q)
			l = []
			for i in range(ql):
				x = q.popleft()
				if x:
					l.append(x.data)
					q.append(x.left)
					q.append(x.right)
			if l:
				res = max(res, sum(l))
		return res


class Solution:

	def maxLevelSum(self, root):
		global a, m
		a = []
		m = -1

		def S(root, level):
			global a, m
			if not root:
				return 0
			if level > m:
				a.append([])
				m = level
			a[level].append(root.data)
			S(root.left, level + 1)
			S(root.right, level + 1)
		S(root, 0)
		k = []
		for i in a:
			k.append(sum(i))
		return max(k)


import sys

class Solution:

	def maxLevelSum(self, root):
		max_sum = -sys.maxsize
		q = [root]
		while q:
			size = len(q)
			summ = 0
			for _ in range(size):
				node = q.pop(0)
				summ += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if summ > max_sum:
				max_sum = summ
		return max_sum


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
		height = self.getHight(root)
		i = 1
		maxsum = 0
		while i <= height:
			tempsum = self.levelOrderTravesal(root, i, 0)
			if tempsum > maxsum:
				maxsum = tempsum
			i += 1
		return maxsum

	def levelOrderTravesal(self, root, level, sumlevel):
		if root is None:
			return sumlevel
		if level == 1:
			sumlevel += root.data
		elif level > 1:
			sumlevel += self.levelOrderTravesal(root.left, level - 1, sumlevel)
			sumlevel += self.levelOrderTravesal(root.right, level - 1, sumlevel)
		return sumlevel

	def getHight(self, root):
		if root is None:
			return 0
		leftHight = 1 + self.getHight(root.left)
		rightheight = 1 + self.getHight(root.right)
		return max(leftHight, rightheight)


class Solution:

	def maxLevelSum(self, root):
		if not root:
			return False
		ans = []
		res = []
		q = deque([root])
		while q:
			level = []
			for _ in range(len(q)):
				node = q.popleft()
				level.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			ans.append(level)
		for a in ans:
			res.append(sum(a))
		return max(res)


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return 0
		q = deque()
		Sum = 0
		Max = -99999999999999
		q.append(root)
		while q:
			n = len(q)
			Sum = 0
			for i in range(n):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				Sum = Sum + node.data
			if Sum > Max:
				Max = Sum
		return Max


from math import inf
from collections import deque

class Solution:

	def maxLevelSum(self, root):
		max_sum = -inf
		q = deque([root])
		while q:
			lvl_sum = 0
			for _ in range(len(q)):
				node = q.popleft()
				lvl_sum += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			max_sum = max(max_sum, lvl_sum)
		return max_sum


class Solution:

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


class Solution:

	def maxLevelSum(self, root):
		res = -10 ** 5
		queue = [root]
		while queue:
			s = 0
			length = len(queue)
			while length > 0:
				node = queue.pop(0)
				s += node.data
				if node.left != None:
					queue.append(node.left)
				if node.right != None:
					queue.append(node.right)
				length -= 1
			if s > res:
				res = s
		return res


class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return []
		l = deque([root])
		l2 = []
		while len(l) > 0:
			l1 = []
			y = len(l)
			for i in range(y):
				x = l.popleft()
				if x.left:
					l.append(x.left)
				if x.right:
					l.append(x.right)
				l1.append(x.data)
			l2.append(sum(l1))
		return max(l2)


class Solution:

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


from queue import Queue

class Solution:

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


class Solution:

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


class Solution:

	def maxLevelSum(self, root):
		level = []
		q = []
		q.append(root)
		while len(q):
			t = len(q)
			temp = []
			while t > 0:
				t -= 1
				s = q.pop(0)
				if s.right:
					q.append(s.right)
				if s.left:
					q.append(s.left)
				temp.append(s.data)
			level.append(sum(temp))
		return max(level)


class Solution:

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


from collections import deque

class Solution:

	def maxLevelSum(self, root):
		ans = -10 ** 9
		if root is None:
			return ans
		queue = deque()
		queue.append(root)
		while len(queue):
			temp = 0
			for i in range(len(queue)):
				node = queue.popleft()
				temp += node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			ans = max(ans, temp)
		return ans


from collections import deque

class Solution:

	def maxLevelSum(self, root):

		def solve(root):
			if root is None:
				return
			Q = deque()
			Q.appendleft(root)
			maxi = float('-inf')
			while Q:
				sz = len(Q)
				sum = 0
				for _ in range(sz):
					node = Q.pop()
					sum += node.data
					if node.left:
						Q.appendleft(node.left)
					if node.right:
						Q.appendleft(node.right)
				maxi = max(maxi, sum)
			return maxi
		return solve(root)


class Solution:

	def maxLevelSum(self, root):
		q = [[root, 0]]
		s = {}
		c = 0
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			if g in s:
				s[g] += t.data
			else:
				s[g] = t.data
			if t.left:
				q.append([t.left, g + 1])
			if t.right:
				q.append([t.right, g + 1])
			c += 1
		m = -9999999999
		for i in s:
			if s[i] > m:
				m = s[i]
		return m


import sys
from collections import defaultdict as dd

class Solution:

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

		def x(root, lvl):
			if root is None:
				return
			d[lvl] += [root.data]
			return x(root.left, lvl + 1) or x(root.right, lvl + 1)
		x(root, 0)
		mx = -sys.maxsize
		for (k, v) in d.items():
			D[k] = sum(v)
		return max(list(D.values()))

	def maxLevelSum_(self, root):
		if root is None:
			return root
		q = [root]
		mx = -sys.maxsize
		while q:
			sm = 0
			for i in range(len(q)):
				curr = q.pop(0)
				sm = sm + curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			mx = max(mx, sm)
		return mx


import sys

class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return root
		q = [root]
		mx = -sys.maxsize
		while q:
			sm = 0
			for i in range(len(q)):
				curr = q.pop(0)
				sm = sm + curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			mx = max(mx, sm)
		return mx


class Node:

	def __init__(self, value):
		self.left = None
		self.data = value
		self.right = None

class Solution:

	def maxLevelSum(self, root):
		if root is None:
			return None
		else:
			ans = []
			import collections
			q = collections.deque()
			q.append(root)
			while q:
				count = 0
				for i in range(len(q)):
					node = q.popleft()
					if node:
						count = count + node.data
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				ans.append(count)
		return max(ans)


class Solution:

	def maxLevelSum(self, root):
		q = []
		res = []
		q.append(root)
		while q:
			count = len(q)
			ans = []
			while count:
				temp = q.pop(0)
				ans.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				count -= 1
			res.append(ans)
		maxi = -99999999
		for i in res:
			maxi = max(maxi, sum(i))
		return maxi


class Solution:

	def maxLevelSum(self, root):
		q = []
		q.append(root)
		ans = -9999999
		while len(q) != 0:
			size = len(q)
			temp = 0
			while size > 0:
				x = q.pop(0)
				temp += x.data
				if x.left != None:
					q.append(x.left)
				if x.right != None:
					q.append(x.right)
				size -= 1
			ans = max(ans, temp)
		return ans