Given a binary tree, find the largest value in each level.
Example 1:
Input:
        1
       / \
      2   3 
Output:
1 3
Explanation:
At 0 level, values of nodes are {1}
                 Maximum value is 1
At 1 level, values of nodes are {2,3}
                Maximum value is 3
Example 2:
Input:
        4
       / \
      9   2
     / \   \
    3   5   7 
Output:
4 9 7
Explanation:
At 0 level, values of nodes are {4}
                 Maximum value is 4
At 1 level, values of nodes are {9,2}
                 Maximum value is 9
At 2 level, values of nodes are {3,5,7}
                 Maximum value is 7
 
Your Task:
You don't need to read input or print anything.Your task is to complete the function maximumValue() that takes root node as input parameter and returns a list of integers containing the maximum value at each level. The size of the resultant list should be equal to the height of the binary tree and result[i] should store the maximum value at level i.
Expected Time Complexity: O(N), where N is the number of nodes.
Expected Auxiliary Space: O(H), where H is the height of binary tree.
Constraints:
1 ≤ Number of nodes ≤ 10^4
1 ≤ Data of a node ≤ 10^5

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Implementation
Skill types: Data structures
Expected Time Complexity: O(N), where N is the number of nodes.
Expected Auxiliary Space: O(H), where H is the height of binary tree.

Starter code:
#User function Template for python3

'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    def maximumValue(self,node):

        # code here

Solutions:
class Solution:

	def maximumValue(self, node):
		ans = []
		m = -1
		q = deque([node, None])
		while True:
			x = q.popleft()
			if x:
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
				if x.data > m:
					m = x.data
			else:
				ans.append(m)
				m = -1
				if q:
					q.append(None)
				else:
					return ans


class Solution:

	def maximumValue(self, node):
		d = {}

		def preo(root, l):
			if root == None:
				return root
			try:
				d[l] = max(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)
		a = []
		try:
			i = 0
			while True:
				a.append(d[i])
				i += 1
		except:
			return a


class Solution:

	def maximumValue(self, node):
		queue = [[root]]
		ans = [root.data]
		while queue:
			level = queue.pop(0)
			temp = []
			maxi = -float('inf')
			for node in level:
				if node.left:
					temp.append(node.left)
					if maxi < node.left.data:
						maxi = node.left.data
				if node.right:
					temp.append(node.right)
					if maxi < node.right.data:
						maxi = node.right.data
			if temp:
				queue.append(temp)
				ans.append(maxi)
		return ans


class Solution:

	def maximumValue(self, node):
		q = [node]
		ans = []
		while len(q) > 0:
			l = len(q)
			maxv = -sys.maxsize
			for _ in range(l):
				temp = q[0]
				q.pop(0)
				maxv = max(maxv, temp.data)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
			ans.append(maxv)
		return ans


from collections import deque

class Solution:

	def maximumValue(self, root):
		q = deque()
		ans = []
		q.append(root)
		while q:
			maxi = 0
			for i in range(len(q)):
				temp = q.popleft()
				maxi = max(maxi, temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			ans.append(maxi)
		return ans


class Solution:

	def maximumValue(self, node):
		ans = [node.data]
		queue = [node]
		while queue:
			temp = float('-inf')
			size = len(queue)
			for i in range(size):
				x = queue.pop(0)
				if x.left:
					queue.append(x.left)
					temp = max(temp, x.left.data)
				if x.right:
					queue.append(x.right)
					temp = max(temp, x.right.data)
			ans.append(temp)
		ans.pop()
		return ans


class Solution:

	def maximumValue(self, node):
		out = [[node.data]]
		queue = [node, '\n']
		temp = []
		while len(queue) > 1:
			if queue[0] == '\n':
				queue.append('\n')
				queue.pop(0)
				out.append(temp)
				temp = []
				continue
			if queue[0].left:
				queue.append(queue[0].left)
				temp.append(queue[0].left.data)
			if queue[0].right:
				queue.append(queue[0].right)
				temp.append(queue[0].right.data)
			queue.pop(0)
		for i in range(len(out)):
			out[i] = max(out[i])
		return out


from collections import deque

class Solution:

	def maximumValue(self, node):
		out = []
		if node is None:
			return out
		q = []
		q.append(node)
		l = []
		while len(q) > 0:
			n = len(q)
			while n > 0:
				temp = q.pop(0)
				if temp.right is not None:
					q.append(temp.right)
				if temp.left is not None:
					q.append(temp.left)
				l.append(temp.data)
				n -= 1
			out.append(max(l))
			l = []
		return out


class Solution:

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


class Solution:

	def maximumValue(self, node):
		q = [node]
		ans = []
		while len(q) > 0:
			l = len(q)
			maxv = q[0].data
			while l > 0:
				temp = q[0]
				q.pop(0)
				maxv = max(maxv, temp.data)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				l -= 1
			ans.append(maxv)
		return ans


from collections import deque

class Solution:

	def maximumValue(self, node):
		queue = deque([node])
		ans = []
		while queue:
			level_max = 0
			for _ in range(len(queue)):
				nd = queue.popleft()
				level_max = max(nd.data, level_max)
				if nd.left:
					queue.append(nd.left)
				if nd.right:
					queue.append(nd.right)
			ans.append(level_max)
		return ans


class Solution:

	def fun(self, root, digit, ans):
		if root == None:
			return
		if digit <= len(ans):
			ans.append([])
		ans[digit].append(root.data)
		self.fun(root.left, digit + 1, ans)
		self.fun(root.right, digit + 1, ans)

	def maximumValue(self, node):
		ans = []
		self.fun(root, 0, ans)
		l = []
		for i in ans:
			if len(i) != 0:
				l.append(max(i))
		return l


class Solution:

	def find(self, root, c, arr):
		if root == None:
			return
		if c == len(arr):
			arr.append(root.data)
		else:
			arr[c] = max(arr[c], root.data)
		self.find(root.left, c + 1, arr)
		self.find(root.right, c + 1, arr)

	def maximumValue(self, node):
		arr = []
		self.find(root, 0, arr)
		return arr


class Solution:

	def maximumValue(self, node):
		hash = {}
		mx = [0] * 1

		def fun(root, level):
			if root == None:
				return
			mx[0] = max(mx[0], level)
			if level not in hash:
				hash[level] = root.data
			else:
				hash[level] = max(root.data, hash[level])
			fun(root.left, level + 1)
			fun(root.right, level + 1)
		fun(root, 0)
		lis = []
		for i in range(mx[0] + 1):
			lis.append(hash[i])
		return lis


class Solution:

	def maximumValue(self, node):

		def helper(root):
			ans = []
			q = []
			t = 0
			if not root:
				return ans
			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 = max(t, a.data)
				ans.append(t)
				t = 0
			return ans
		return helper(node)


class Solution:

	def recursive_check(self, resArr, node, level):
		if len(resArr) == level:
			resArr.append(node.data)
		else:
			resArr[level] = max(node.data, resArr[level])
		if node.left != None:
			self.recursive_check(resArr, node.left, level + 1)
		if node.right != None:
			self.recursive_check(resArr, node.right, level + 1)

	def maximumValue(self, node):
		resArr = []
		self.recursive_check(resArr, node, 0)
		return resArr


class Solution:

	def levelOrder(self, Q, arr):
		while len(Q) != 0:
			max_ = -90000
			for i in range(len(Q)):
				popped = Q.pop(0)
				if popped.data > max_:
					max_ = popped.data
				if popped.left:
					Q.append(popped.left)
				if popped.right:
					Q.append(popped.right)
			arr.append(max_)
		return arr

	def maximumValue(self, node):
		Q = [node]
		arr = []
		arr = self.levelOrder(Q, arr)
		return arr


from collections import deque

class Solution:

	def maximumValue(self, node):
		ans = []
		dq = deque()
		dq.append(node)
		while len(dq) > 0:
			maxi = 0
			currsize = len(dq)
			for i in range(currsize):
				temp = dq.popleft()
				maxi = max(maxi, temp.data)
				if temp.left != None:
					dq.append(temp.left)
				if temp.right != None:
					dq.append(temp.right)
			ans.append(maxi)
		return ans


class Solution:

	def maximumValue(self, node):
		q = [root]
		ans = []
		while q:
			l = len(q)
			max_ans = -1000000000.0
			for i in range(l):
				temp = q.pop(0)
				max_ans = max(max_ans, temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			ans.append(max_ans)
		return ans


class Solution:

	def maximumValue(self, node):
		(q, res) = ([], [])
		q.append(node)
		while len(q):
			queue = []
			max_val = 0
			for node in q:
				if node is None:
					continue
				max_val = max(max_val, node.data)
				queue.append(node.left)
				queue.append(node.right)
			q = queue
			if max_val:
				res.append(max_val)
		return res


class Solution:

	def maximumValue(self, node):
		self.dic = {}

		def traverse(root, level):
			if not root:
				return
			if level in self.dic:
				if root.data > self.dic[level]:
					self.dic[level] = root.data
			else:
				self.dic[level] = root.data
			traverse(root.left, level + 1)
			traverse(root.right, level + 1)
		traverse(root, 0)
		ans = []
		for i in range(len(self.dic)):
			ans.append(self.dic[i])
		return ans


class Solution:

	def maximumValue(self, node):
		q = []
		ans = []
		q.append(node)
		while len(q):
			count = len(q)
			maxi = -1
			while count > 0:
				n = q.pop(0)
				if maxi < n.data:
					maxi = n.data
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
				count -= 1
			ans.append(maxi)
		return ans


class Solution:

	def solve(self, node, level, answer):
		if node is None:
			return
		if level == len(answer):
			answer.append(node.data)
		else:
			answer[level] = max(answer[level], node.data)
		self.solve(node.left, level + 1, answer)
		self.solve(node.right, level + 1, answer)

	def maximumValue(self, node):
		answer = []
		self.solve(node, 0, answer)
		return answer


class Solution:

	def maximumValue(self, node):
		li = []
		que = [node]
		li.append(node.data)
		while que:
			ans = 0
			for i in range(len(que)):
				root = que.pop(0)
				if root.left:
					que.append(root.left)
					ans = max(ans, root.left.data)
				if root.right:
					que.append(root.right)
					ans = max(ans, root.right.data)
			if ans != 0:
				li.append(ans)
		return li


class Solution:

	def maximumValue(self, node):
		lvls = {}
		max_lvl = 0

		def recursive(root, lvl=1):
			nonlocal lvls, max_lvl
			if root is None:
				return
			max_lvl = max(max_lvl, root.data)
			if lvl not in lvls:
				lvls[lvl] = root.data
			else:
				lvls[lvl] = max(lvls[lvl], root.data)
			recursive(root.left, lvl + 1)
			recursive(root.right, lvl + 1)
		recursive(root)
		ans = []
		lvl = 1
		while lvl in lvls:
			ans.append(lvls[lvl])
			lvl += 1
		return ans


class Solution:

	def maximumValue(self, node):
		q = []
		q.append(node)
		res = []
		while q:
			n = len(q)
			mx = 0
			for i in q:
				if mx < i.data:
					mx = i.data
			res.append(mx)
			while n > 0:
				tmp = q.pop(0)
				if tmp.left:
					q.append(tmp.left)
				if tmp.right:
					q.append(tmp.right)
				n -= 1
		return res


class Solution:

	def maximumValue(self, node):
		ans = []

		def dfs(r=node, level=0):
			nonlocal ans
			if not r:
				return
			if level >= len(ans):
				ans.append(r.data)
			else:
				ans[level] = max(ans[level], r.data)
			dfs(r.left, level + 1)
			dfs(r.right, level + 1)
		dfs()
		return ans


class Solution:

	def maximumValue(self, node):
		output = []
		self.helper(node, 0, output)
		return output

	def helper(self, node, level, arr):
		if node == None:
			return
		if len(arr) == level:
			arr.append(float('-inf'))
		arr[level] = max(arr[level], node.data)
		self.helper(node.left, level + 1, arr)
		self.helper(node.right, level + 1, arr)
		return


class Solution:

	def maximumValue(self, node):

		def dfs(root):
			if root is None:
				return [root.data]
			q = deque([root])
			l1 = []
			depth = 0
			while q:
				qlen = len(q)
				ans = 0
				for i in range(qlen):
					root = q.popleft()
					ans = max(ans, root.data)
					if root.left:
						q.append(root.left)
					if root.right:
						q.append(root.right)
				depth += 1
				l1.append(ans)
			return l1
		return dfs(root)


class Solution:

	def maximumValue(self, node):
		q = [root]
		lis = []
		while q:
			res = []
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				res.append(node.data)
			lis.append(max(res))
		return lis


import collections

class Solution:

	def maximumValue(self, node):
		res = []
		q = collections.deque()
		q.append(root)
		while q:
			l = []
			for i in range(len(q)):
				x = q.popleft()
				if x:
					l.append(x.data)
					q.append(x.left)
					q.append(x.right)
			if l:
				res.append(l)
		a = []
		for k in res:
			x = max(k)
			a.append(x)
		return a


from collections import OrderedDict

class Solution:

	def maximumValue(self, node):
		p = []
		q = []
		p.append(0)
		q.append(root)
		g = {}
		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)
		m = OrderedDict(sorted(g.items()))
		ans = []
		for x in m:
			ans.append(max(m[x]))
		return ans


class Solution:

	def maximumValue(self, node):

		def traversal(root, level):
			if root == None:
				return None
			if level not in dict1:
				dict1[level] = root.data
			elif root.data > dict1[level]:
				dict1[level] = root.data
			if root.left:
				traversal(root.left, level + 1)
			if root.right:
				traversal(root.right, level + 1)
		dict1 = dict()
		traversal(root, 0)
		return list(dict1.values())


def helper(res, root, d):
	if not root:
		return
	if d == len(res):
		res.append(root.data)
	else:
		res[d] = max(res[d], root.data)
	helper(res, root.left, d + 1)
	helper(res, root.right, d + 1)

def largestValues(root):
	res = []
	helper(res, root, 0)
	return res

class Solution:

	def maximumValue(self, node):
		return largestValues(node)


class Solution:

	def maximumValueBFS(self, node):
		ans = []
		q = []
		q.append(node)
		while q:
			levelmax = 0
			for i in range(len(q)):
				curr = q.pop(0)
				if curr.data > levelmax:
					levelmax = curr.data
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
			ans.append(levelmax)
		return ans

	def maximumValue(self, node):
		ans = []

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


class Solution:

	def maximumValue(self, node):
		ans = []
		q = []
		q.append(node)
		while q:
			levelmax = 0
			for i in range(len(q)):
				curr = q.pop(0)
				if curr.data > levelmax:
					levelmax = curr.data
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
			ans.append(levelmax)
		return ans


class Solution:

	def __init__(self):
		self.my_list = list()

	def seek(self, node, story):
		if node:
			if len(self.my_list) == story:
				self.my_list.append(node.data)
			else:
				self.my_list[story] = max(self.my_list[story], node.data)
			if node.left != None:
				self.seek(node.left, story + 1)
			if node.right != None:
				self.seek(node.right, story + 1)

	def maximumValue(self, node):
		self.seek(node, 0)
		return self.my_list


class Solution:

	def hei(self, node, H, k):
		if node:
			H[k] = []
			self.hei(node.left, H, k + 1)
			self.hei(node.right, H, k + 1)

	def dfs(self, H, node, k):
		if node:
			H[k].append(node.data)
			self.dfs(H, node.left, k + 1)
			self.dfs(H, node.right, k + 1)

	def maximumValue(self, node):
		H = dict()
		k = 0
		self.hei(node, H, k)
		self.dfs(H, node, k)
		res = []
		for i in H:
			res.append(max(H[i]))
		return res


class Solution:

	def maximumValue(self, node):
		queue = []
		maxi = 0
		high = []
		queue.append(node)
		queue.append('#')
		while len(queue) > 0:
			k = queue.pop(0)
			if k == '#':
				queue.append('#')
				high.append(maxi)
				maxi = 0
				if len(queue) < 2:
					break
			else:
				if k.data > maxi:
					maxi = k.data
				if k.left != None:
					queue.append(k.left)
				if k.right != None:
					queue.append(k.right)
		return high


class Solution:

	def maximumValue(self, node):
		q = list()
		q.append(node)
		ans = list()
		while q:
			n = len(q)
			maxi = -1
			while n:
				cur = q.pop(0)
				maxi = max(maxi, cur.data)
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
				n -= 1
			ans.append(maxi)
		return ans


class Solution:

	def maximumValue(self, node):
		q = []
		max = -10000
		q.append(root)
		final = []
		q.append('$')
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					final.append(max)
					max = -10000
				else:
					final.append(max)
			else:
				if t.data >= max:
					max = t.data
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return final


class Solution:

	def maximumValue(self, node):
		found = [node]
		next_level = []
		result = [node.data]
		while len(found) != 0:
			x = found.pop(0)
			if x.right:
				next_level.append(x.right)
			if x.left:
				next_level.append(x.left)
			if len(found) == 0:
				(next_level, found) = (found, next_level)
				if len(found) != 0:
					result.append(max([v.data for v in found]))
		return result


class Solution:

	def maximumValue(self, node):
		if not node:
			return ''
		lvl = 1
		queue = {}
		arr = {}
		queue[lvl] = [node]
		while len(queue) > 0:
			loop = queue.pop(lvl)
			arr[lvl] = 0
			for a in loop:
				if a:
					if a.data > arr[lvl]:
						arr[lvl] = a.data
					if a.left:
						if lvl + 1 in queue:
							queue[lvl + 1].append(a.left)
						else:
							queue[lvl + 1] = [a.left]
					if a.right:
						if lvl + 1 in queue:
							queue[lvl + 1].append(a.right)
						else:
							queue[lvl + 1] = [a.right]
			lvl += 1
		s = []
		for (h, v) in arr.items():
			s.append(v)
		return s


class Solution:

	def maximumValue(self, root):
		ans = []
		q = deque()
		q.append(root)
		while q:
			max_ = 0
			for _ in range(len(q)):
				p = q.popleft()
				max_ = max(max_, p.data)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
			ans.append(max_)
		return ans


class Solution:

	def maximumValue(self, node):
		if not node:
			return
		q = deque([root])
		res = []
		while q:
			mx = -float('inf')
			for i in range(len(q)):
				node = q.popleft()
				mx = max(mx, node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			res.append(mx)
		return res


class Solution:

	def maximumValue(self, node):
		global p
		p = []
		global l
		l = 0

		def sol(root, level):
			global p, l
			if not root:
				return
			if l <= level:
				p.append([])
				l = level
			p[level].append(root.data)
			sol(root.left, level + 1)
			sol(root.right, level + 1)
		sol(root, 0)
		k = []
		for i in range(len(p)):
			if p[i] != []:
				k.append(max(p[i]))
		return k


class Solution:

	def maximumValue(self, node):
		if not root:
			return []
		ans = []
		queue = [(node, 0)]
		while queue:
			(curr_node, level) = queue.pop(0)
			if len(ans) == level:
				ans.append(curr_node.data)
			else:
				ans[level] = max(ans[level], curr_node.data)
			if curr_node.left:
				queue.append((curr_node.left, level + 1))
			if curr_node.right:
				queue.append((curr_node.right, level + 1))
		return ans


class Solution:

	def maximumValue(self, node):
		dict = {}

		def leftviewutil(dict, level, roots):
			if roots == None:
				return
			if dict.get(level) == None:
				dict[level] = roots.data
			elif dict.get(level) < roots.data:
				dict[level] = roots.data
			leftviewutil(dict, level + 1, roots.left)
			leftviewutil(dict, level + 1, roots.right)
		leftviewutil(dict, 0, node)
		return dict.values()


class Solution:

	def maximumValue(self, node):
		levels = []

		def bfs(node, level):
			nonlocal levels
			if not node:
				return
			if level >= len(levels):
				levels.append([node.data])
			else:
				levels[level].append(node.data)
			if node.left:
				bfs(node.left, level + 1)
			if node.right:
				bfs(node.right, level + 1)
		bfs(node, 0)
		return [max(level) for level in levels]


from collections import deque

class Solution:

	def maximumValue(self, root):
		if root is None:
			return []
		q = deque()
		q.append(root)
		result = []
		while q:
			i = 0
			size = len(q)
			max_v = 0
			while i < size:
				node = q.popleft()
				max_v = max(max_v, node.data)
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
				i += 1
			result.append(max_v)
		return result


class Solution:

	def maximumValue(self, node):
		(queue, level) = ([], [])
		(len_level, len_next_level) = (1, 0)
		queue.append(node)
		while len(queue) != 0:
			n = queue.pop(0)
			level.append(n.data)
			len_level -= 1
			if n.left is not None:
				len_next_level += 1
			if n.right is not None:
				len_next_level += 1
			if len_level == 0:
				minimum = max(level)
				yield minimum
				level.clear()
				len_level = len_next_level
				len_next_level = 0
			if n.left is not None:
				queue.append(n.left)
			if n.right is not None:
				queue.append(n.right)


class Solution:

	def traverse(self, node, ans, level):
		if node is None:
			return
		if len(ans) >= level:
			ans[level - 1] = max(node.data, ans[level - 1])
		else:
			ans.append(node.data)
		self.traverse(node.left, ans, level + 1)
		self.traverse(node.right, ans, level + 1)

	def dfs(self, node, ans):
		if node is None:
			return
		stack = [(node, 1)]
		while stack:
			(n, level) = stack.pop()
			if len(ans) >= level:
				ans[level - 1] = max(n.data, ans[level - 1])
			else:
				ans.append(n.data)
			if n.left is not None:
				stack.append((n.left, level + 1))
			if n.right is not None:
				stack.append((n.right, level + 1))

	def maximumValue(self, node):
		ans = []
		self.dfs(node, ans)
		return ans


class Solution:

	def maximumValue(self, node):
		ans = []
		if not node:
			return []
		st = deque([node])
		helper = []
		while st:
			n = len(st)
			res = -1000000000.0
			row = []
			while n:
				ele = st.popleft()
				if ele.left:
					st.append(ele.left)
				if ele.right:
					st.append(ele.right)
				n = n - 1
				row.append(ele.data)
				res = max(res, ele.data)
			ans.append(res)
		return ans


from collections import deque

def levelOrder(root):
	res = []
	q = deque()
	q.append(root)
	while q:
		qlen = len(q)
		level = []
		for i in range(qlen):
			node = q.popleft()
			if node:
				level.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if level:
			res.append(level)
	return res

class Solution:

	def maximumValue(self, node):
		ans = []
		res = levelOrder(root)
		for i in range(len(res)):
			ans.append(max(res[i]))
		return ans


class Solution:

	def visit(self, node, ans, depth):
		if node is None:
			return
		ans[depth] = max(ans.get(depth, 0), node.data)
		self.visit(node.left, ans, depth + 1)
		self.visit(node.right, ans, depth + 1)
		return

	def maximumValue(self, node):
		ans = {}
		self.visit(node, ans, 0)
		return [ans[i] for i in sorted(ans)]


class Solution:

	def maximumValue(self, node):
		q = [node]
		ans = []
		while q:
			maxi = 0
			for i in range(len(q)):
				nodeValue = q.pop(0)
				maxi = max(maxi, nodeValue.data)
				if nodeValue.left:
					q.append(nodeValue.left)
				if nodeValue.right:
					q.append(nodeValue.right)
			ans.append(maxi)
		return ans


from collections import deque

class Solution:

	def maximumValue(self, node):
		q = deque()
		q.append(node)
		ans = []
		while q:
			nc = len(q)
			maxval = 0
			while nc > 0:
				node = q.popleft()
				maxval = max(maxval, node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				nc -= 1
			ans.append(maxval)
		return ans


class Solution:

	def maximumValueUtil(self, node, di, level):
		if node == None:
			return
		elif level in di.keys():
			di[level] = di[level] if di[level] > node.data else node.data
		else:
			di[level] = node.data
		Solution.maximumValueUtil(self, node.left, di, level + 1)
		Solution.maximumValueUtil(self, node.right, di, level + 1)
		return

	def maximumValue(self, node):
		di = dict()
		Solution.maximumValueUtil(self, node, di, 0)
		return di.values()


import collections
import math

class Solution:

	def maximumValue(self, node):
		result = []
		if root is None:
			return res
		q = collections.deque()
		q.append(root)
		while q:
			max_at_level = -math.inf
			level = len(q)
			for i in range(level):
				node = q.popleft()
				max_at_level = max(max_at_level, node.data)
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
			result.append(max_at_level)
		return result


class Solution:

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


class Solution:

	def maximumValue(self, node):
		l = []

		def find(node, lv):
			if node is None:
				return
			if lv == len(l):
				l.append(node.data)
			else:
				l[lv] = max(l[lv], node.data)
			find(node.left, lv + 1)
			find(node.right, lv + 1)
		find(node, 0)
		return l


class Solution:

	def maximumValue(self, node):
		dct = []

		def Walker(nod, depth):
			if nod is not None:
				if depth == len(dct):
					dct.append(nod.data)
				else:
					dct[depth] = max(dct[depth], nod.data)
				Walker(nod.left, depth + 1)
				Walker(nod.right, depth + 1)
		Walker(root, 0)
		return dct


class Solution:

	def maximumValue(self, node):
		dct = dict()

		def Walker(nod, depth):
			if nod is not None:
				dct[depth] = max(dct.get(depth, float('-inf')), nod.data)
				Walker(nod.left, depth + 1)
				Walker(nod.right, depth + 1)
		Walker(root, 0)
		return [dct[i] for i in range(max(dct.keys()) + 1)]


class Solution:

	def maximumValue(self, node):
		(val, ans) = ([node], [])
		while len(val) != 0:
			val1 = []
			temp = val[0].data
			for i in range(1, len(val)):
				temp = max(temp, val[i].data)
			for i in val:
				if i.left != None:
					val1.append(i.left)
				if i.right != None:
					val1.append(i.right)
			val = val1.copy()
			ans.append(temp)
		return ans


class Solution:

	def maximumValue(self, root):
		listt = []
		level_listt = []
		res = []
		listt.append(root)
		while True:
			for i in range(len(listt)):
				level_listt.append(listt[i].data)
			res.append(max(level_listt))
			n = len(listt)
			for i in range(n):
				root = listt.pop(0)
				level_listt.pop(0)
				if root.left:
					listt.append(root.left)
				if root.right:
					listt.append(root.right)
			if len(listt) == 0:
				break
		return res


class Solution:

	def maximumValue(self, node):
		q = []
		ans = []
		q.append(node)
		while q:
			n = len(q)
			m = -1
			while n > 0:
				temp = q[0]
				q.pop(0)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				m = max(m, temp.data)
				n -= 1
			ans.append(m)
		return ans


class Node:

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

class Solution:

	def maximumValue(self, node):
		l = []
		l.append(node)
		res = []
		while l:
			level = []
			for i in range(len(l)):
				node = l.pop(0)
				if node:
					level.append(node.data)
				if node.left:
					l.append(node.left)
				if node.right:
					l.append(node.right)
			if level:
				res.append(max(level))
		return res


class Solution:

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

	def maximumValue(self, node, height=0):
		if node is None:
			return
		if height in self.d.keys():
			self.d[height] = max(self.d[height], node.data)
		else:
			self.d[height] = node.data
		self.maximumValue(node.left, height + 1)
		self.maximumValue(node.right, height + 1)
		return self.d.values()


class Solution:

	def maximumValue(self, node):
		ans = []
		if root is None:
			return None
		q = []
		q.append(root)
		while len(q) > 0:
			n = len(q)
			maxi = 0
			for i in range(n):
				curr = q.pop(0)
				maxi = max(maxi, curr.data)
				if curr.left is not None:
					q.append(curr.left)
				if curr.right is not None:
					q.append(curr.right)
			ans.append(maxi)
		return ans