Given below is a binary tree. The task is to print the top view of binary tree. Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. For the given below tree
       1
    /     \
   2       3
  /  \    /   \
4    5  6   7
Top view will be: 4 2 1 3 7
Note: Return nodes from leftmost node to rightmost node. Also if 2 nodes are outside the shadow of the tree and are at same position then consider the extreme ones only(i.e. leftmost and rightmost). 
For ex - 1 2 3 N 4 5 N 6 N 7 N 8 N 9 N N N N N will give 8 2 1 3 as answer. Here 8 and 9 are on the same position but 9 will get shadowed.
Example 1:
Input:
      1
   /    \
  2      3
Output: 2 1 3
Example 2:
Input:
       10
    /      \
  20        30
 /   \    /    \
40   60  90    100
Output: 40 20 10 30 100
Your Task:
Since this is a function problem. You don't have to take input. Just complete the function topView() that takes root node as parameter and returns a list of nodes visible from the top view from left to right.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Node Data ≤ 10^{5}

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries
Skill types: Data structures

Range queries
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



# Tree Node

# class Node:

#     def __init__(self, val):

#         self.right = None

#         self.data = val

#         self.left = None



class Solution:

    

    #Function to return a list of nodes visible from the top view 

    #from left to right in Binary Tree.

    def topView(self,root):

        

        # code here

Solutions:
from collections import defaultdict

class Solution:

	def topView(self, root):
		mp = defaultdict(list)

		def traversal(node, x, y, mp):
			if node is None:
				return
			traversal(node.left, x - 1, y + 1, mp)
			traversal(node.right, x + 1, y + 1, mp)
			mp[x, y].append(node.data)
		traversal(root, 0, 0, mp)
		x = []
		i = {}
		for (k, v) in sorted(mp.items()):
			if k[0] not in i:
				i[k[0]] = 1
				x.append(v[0])
		return x


class Solution:

	def topView(self, root):

		def printTopView(root, h_dist, v_dist, d):
			if root is None:
				return
			if h_dist not in d or v_dist < d[h_dist][1]:
				d[h_dist] = (root.data, v_dist)
			printTopView(root.left, h_dist - 1, v_dist + 1, d)
			printTopView(root.right, h_dist + 1, v_dist + 1, d)
		d = {}
		printTopView(root, 0, 0, d)
		ans = []
		for h_dist in sorted(d.keys()):
			ans.append(d[h_dist][0])
		return ans


from collections import OrderedDict

class Solution:

	def topView(self, root):
		ans = []
		map = OrderedDict()
		queue = []
		if root is None:
			return ans
		i = 1
		(minn, maxx) = (0, 0)
		queue.append((root, 0))
		while len(queue) > 0:
			it = queue.pop(0)
			line = it[1]
			node = it[0]
			if line not in map.keys():
				map.update({line: node.data})
			if node.left is not None:
				queue.append((node.left, line - 1))
				minn = min(minn, line - 1)
			if node.right is not None:
				queue.append((node.right, line + 1))
				maxx = max(maxx, line + 1)
		myKeys = list(map.keys())
		myKeys.sort()
		sorted_dict = {i: map[i] for i in myKeys}
		for i in range(minn, maxx + 1):
			ans.append(map[i])
		return ans


from collections import deque, defaultdict

class Solution:

	def topView(self, root):
		que = deque()
		nodes = defaultdict()
		que.append([root, 0])
		while que:
			(curr, ind) = que.popleft()
			if ind not in nodes.keys():
				nodes[ind] = curr.data
			if curr.left:
				que.append([curr.left, ind - 1])
			if curr.right:
				que.append([curr.right, ind + 1])
		out = list(nodes.keys())
		out.sort()
		return [nodes[k] for k in out]


class Solution:

	def topView(self, root):
		if root is None:
			return []
		d = {}
		q = []
		levels = []
		q.append(root)
		levels.append(0)
		while q:
			curr = q.pop(0)
			level = levels.pop(0)
			if level not in d:
				d[level] = curr.data
			if curr.left != None:
				q.append(curr.left)
				levels.append(level - 1)
			if curr.right != None:
				q.append(curr.right)
				levels.append(level + 1)
		return [d[i] for i in sorted(d.keys())]


from collections import deque

class Solution:

	def topView(self, root):
		if not root:
			return []
		d = {}
		q = deque([(root, 0)])
		while q:
			(x, l) = q.popleft()
			if l not in d:
				d[l] = x.data
			if x.left:
				q.append((x.left, l - 1))
			if x.right:
				q.append((x.right, l + 1))
		return [d[x] for x in sorted(d)]


class Solution:

	def topView(self, root):
		if root == None:
			return []
		hashmap = {}
		d = {}
		queue = []
		queue.append([root, 0])
		while queue:
			node = queue.pop(0)
			cnode = node[0]
			value = cnode.data
			line = node[1]
			if line not in hashmap:
				hashmap[line] = value
			if cnode.left:
				queue.append([cnode.left, line - 1])
			if cnode.right:
				queue.append([cnode.right, line + 1])
		res = []
		d = sorted(hashmap.items())
		for i in d:
			res.append(i[1])
		return res


class Solution:

	def topView(self, root):
		d = dict()
		if root == None:
			return []
		q = [(root, 0)]
		while q:
			(nod, h) = q.pop(0)
			if h not in d:
				d[h] = nod.data
			if nod.left:
				q.append([nod.left, h - 1])
			if nod.right:
				q.append([nod.right, h + 1])
		d = sorted(d.items())
		ans = []
		for (k, v) in d:
			ans.append(v)
		return ans


class Solution:

	def topView(self, root):
		(map, queue, res, hd) = ({}, [], [], 0)
		if root is None:
			return
		queue.append((root, 0))
		while queue:
			(curr, hd) = queue.pop(0)
			if hd not in map.keys():
				map[hd] = [curr.data]
			if curr.left:
				queue.append((curr.left, hd - 1))
			if curr.right:
				queue.append((curr.right, hd + 1))
		for i in sorted(map):
			res += map[i]
		return res


class Solution:

	def topView(self, root):
		if root is None:
			return []
		queue = deque()
		queue.append([root, 0])
		hashmap = {}
		(mini, maxi) = (0, 0)
		while queue:
			temp = queue.popleft()
			node = temp[0]
			height = temp[1]
			if not height in hashmap:
				hashmap[height] = node.data
			if node.left:
				queue.append([node.left, height - 1])
				mini = min(mini, height - 1)
			if node.right:
				queue.append([node.right, height + 1])
				maxi = max(maxi, height + 1)
		ans = []
		for i in range(mini, maxi + 1):
			ans.append(hashmap[i])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		topnode = {}
		q = deque([(root, 0)])
		while q:
			front = q.popleft()
			(node, hd) = front
			if hd not in topnode:
				topnode[hd] = node.data
			if node.left:
				q.append((node.left, hd - 1))
			if node.right:
				q.append((node.right, hd + 1))
		res = []
		for i in sorted(topnode.keys()):
			res.append(topnode[i])
		return res


from collections import deque

class Solution:

	def topView(self, root):
		if root is None:
			return
		queue = deque()
		queue.append((root, 0))
		ans = {}
		minb = 0
		maxb = 0
		while len(queue) != 0:
			size = len(queue)
			for i in range(size):
				(node, index) = queue[0]
				queue.popleft()
				minb = min(minb, index)
				maxb = max(maxb, index)
				if index not in ans:
					ans[index] = node.data
				if node.left is not None:
					queue.append((node.left, index - 1))
				if node.right is not None:
					queue.append((node.right, index + 1))
		res = []
		for i in range(minb, maxb + 1):
			res.append(ans[i])
		return res


class Solution:

	def topView(self, root):
		res = []
		m = {}

		def dfs(root, row, col):
			if root is None:
				return
			dfs(root.left, row + 1, col - 1)
			dfs(root.right, row + 1, col + 1)
			if col in m:
				if row in m[col]:
					m[col][row].append(root.data)
				else:
					m[col][row] = [root.data]
			else:
				m[col] = {}
				m[col][row] = [root.data]
		dfs(root, 0, 0)
		for k1 in sorted(m):
			for k2 in sorted(m[k1]):
				res.append(m[k1][k2][0])
				break
		return res


class Solution:

	def topView(self, root):
		ans = []
		queue = deque([(root, 0)])
		views = {}
		min_pos = max_pos = 0
		while queue:
			(node, pos) = queue.popleft()
			if pos not in views:
				views[pos] = node.data
				min_pos = min(min_pos, pos)
				max_pos = max(max_pos, pos)
			if node.left:
				queue.append((node.left, pos - 1))
			if node.right:
				queue.append((node.right, pos + 1))
		for i in range(min_pos, max_pos + 1):
			ans.append(views[i])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		myMap = {}
		queue = deque([(root, 0)])
		while queue:
			(node, hd) = queue.popleft()
			if hd not in myMap:
				myMap[hd] = node.data
			if node.left:
				queue.append((node.left, hd - 1))
			if node.right:
				queue.append((node.right, hd + 1))
		return [myMap[i] for i in sorted(myMap)]


class Solution:

	def topView(self, root):
		queue = [(root, 0)]
		(hd, l, r) = (0, 0, 0)
		left = []
		right = []
		while queue:
			(node, hd) = queue.pop(0)
			temp = []
			if hd < l:
				left = [node.data] + left
				l -= 1
			elif hd > r:
				right.append(node.data)
				r += 1
			if node.left:
				queue.append((node.left, hd - 1))
			if node.right:
				queue.append((node.right, hd + 1))
		return left + [root.data] + right


class Solution:

	def topView(self, root):
		d = {}
		q = []
		res = []
		q.append((root, 0))
		while q:
			(n, l) = q.pop(0)
			if n and l not in d:
				d[l] = n.data
			if n.left:
				q.append((n.left, l - 1))
			if n.right:
				q.append((n.right, l + 1))
		d = sorted(d.items(), key=lambda x: x[0])
		for (k, v) in d:
			res.append(v)
		return res


class Solution:

	def topView(self, root):
		levels = []
		q = []
		d = {}
		levels.append(0)
		q.append(root)
		while len(q) != 0:
			curr = q.pop(0)
			lvl = levels.pop(0)
			if lvl not in d:
				d[lvl] = curr.data
			if curr.left != None:
				q.append(curr.left)
				levels.append(lvl - 1)
			if curr.right != None:
				q.append(curr.right)
				levels.append(lvl + 1)
		ans = []
		for i in sorted(d.keys()):
			ans.append(d[i])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		if root == None:
			return []
		q = deque()
		q.append([root, 0])
		d = dict()
		while q:
			(node, line) = q.popleft()
			if line not in d:
				d[line] = node.data
			if node.left:
				q.append([node.left, line - 1])
			if node.right:
				q.append([node.right, line + 1])
		ans = []
		for k in sorted(d):
			ans.append(d[k])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		if root is None:
			return []
		queue = deque()
		queue.append([root, 0])
		hashmap = {}
		(minn, maxx) = (0, 0)
		while queue:
			temp = queue.popleft()
			node = temp[0]
			height = temp[1]
			if height not in hashmap:
				hashmap[height] = node.data
			if node.left:
				queue.append([node.left, height - 1])
				minn = min(minn, height - 1)
			if node.right:
				queue.append([node.right, height + 1])
				maxx = max(maxx, height + 1)
		ans = []
		for i in range(minn, maxx + 1):
			ans.append(hashmap[i])
		return ans


class Solution:

	def topviewu(self, root, d, vd, lv):
		if not root:
			return
		if vd in d:
			if d[vd][0] > lv:
				d[vd] = (lv, root.data)
		else:
			d[vd] = (lv, root.data)
		self.topviewu(root.left, d, vd - 1, lv + 1)
		self.topviewu(root.right, d, vd + 1, lv + 1)

	def topView(self, root):
		d = dict()
		ans = []
		self.topviewu(root, d, 0, 0)
		for e in sorted(d):
			ans.append(d[e][1])
		return ans


class Solution:

	def topView(self, root):
		vert_map = {}

		def recursive(root, dist=0, lvl=0):
			if root is None:
				return
			if dist in vert_map:
				if vert_map[dist][0] > lvl:
					vert_map[dist] = (lvl, root.data)
			else:
				vert_map[dist] = (lvl, root.data)
			recursive(root.left, dist - 1, lvl + 1)
			recursive(root.right, dist + 1, lvl + 1)
		recursive(root)
		return [vert_map[k][1] for k in sorted(vert_map)]


class Solution:

	def topView(self, root):
		store = {}
		queue = []
		queue.append((root, 0))
		while queue:
			(node, line) = queue.pop(0)
			if line not in store:
				store[line] = node.data
			if node.left:
				queue.append((node.left, line - 1))
			if node.right:
				queue.append((node.right, line + 1))
		res = []
		for (line, val) in sorted(store.items()):
			res.append(val)
		return res


from collections import OrderedDict, deque

class Solution:

	def topView(self, root):
		ans = []
		result_map = {}
		if root == None:
			return ans
		q = deque()
		q.append((root, 0))
		while len(q):
			(node, hd) = q.popleft()
			if result_map.get(hd) == None:
				result_map[hd] = node.data
			if node.left:
				q.append((node.left, hd - 1))
			if node.right:
				q.append((node.right, hd + 1))
		sorted_distances = sorted(result_map.keys())
		for d in sorted_distances:
			ans.append(result_map[d])
		return ans


class Solution:

	def topView(self, root):
		queue = [(root, 0)]
		temp = {0: root.data}
		while queue:
			(node, level) = queue.pop(0)
			if level not in temp:
				temp[level] = node.data
			if node.left != None:
				queue.append((node.left, level - 1))
			if node.right != None:
				queue.append((node.right, level + 1))
		keys = list(temp.keys())
		keys.sort()
		ans = []
		for key in keys:
			ans.append(temp[key])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		X = {}
		queue = deque()
		queue.append([root, 0])
		while queue:
			(node, x) = queue.popleft()
			if x not in X:
				X[x] = node.data
			if node.left:
				queue.append([node.left, x - 1])
			if node.right:
				queue.append([node.right, x + 1])
		answer = []
		for key in sorted(X):
			answer.append(X[key])
		return answer


class Solution:

	def topView(self, root):
		q = []
		h = 0
		q.append([root, h])
		mp = dict()
		mini = 0
		maxi = 0
		while len(q) > 0:
			(node, hd) = q[0]
			q.pop(0)
			if hd not in mp:
				mp[hd] = node.data
			mini = min(mini, hd)
			maxi = max(maxi, hd)
			if node.left:
				q.append([node.left, hd - 1])
			if node.right:
				q.append([node.right, hd + 1])
		a = []
		for i in range(mini, maxi + 1):
			a.append(mp[i])
		return a


class Solution:

	def topView(self, root):
		queue = [(0, 0, root)]
		levelElements = {}
		while queue:
			(col, row, node) = queue.pop(0)
			if col not in levelElements:
				levelElements[col] = node.data
			if node.left:
				queue.append((col - 1, row + 1, node.left))
			if node.right:
				queue.append((col + 1, row + 1, node.right))
		levelElements = sorted(levelElements.items(), key=lambda x: (x[0], x[1]))
		return [i[1] for i in levelElements]
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		if not root:
			return []
		que = deque()
		que.append((0, root))
		dic = {}
		while len(que) != 0:
			(col, temp) = que.popleft()
			if col not in dic:
				dic[col] = temp.data
			if temp.left:
				que.append((col - 1, temp.left))
			if temp.right:
				que.append((col + 1, temp.right))
		result = []
		for v in sorted(dic.keys()):
			result.append(dic[v])
		return result


class Solution:

	def topView(self, root):
		q = []
		res = []
		d = {}
		q.append((root, 0))
		while q:
			(x, y) = q.pop(0)
			if y not in d:
				d[y] = x.data
			if x.left != None:
				q.append((x.left, y - 1))
			if x.right != None:
				q.append((x.right, y + 1))
		for i in sorted(d.keys()):
			res.append(d[i])
		return res


from collections import deque

class Solution:

	def topView(self, root):
		if root is None:
			return []
		queue = deque()
		queue.append([root, 0])
		hashmap = {}
		while queue:
			temp = queue.popleft()
			node = temp[0]
			height = temp[1]
			if not height in hashmap:
				hashmap[height] = node.data
			if node.left:
				queue.append([node.left, height - 1])
			if node.right:
				queue.append([node.right, height + 1])
		ans = []
		for i in sorted(hashmap):
			ans.append(hashmap[i])
		return ans


class Solution:

	def topView(self, root):
		ans = []
		hd = 0
		MIN = 999
		d = dict()
		queue = deque()
		queue.append([root, hd])
		while queue:
			(curr, hd) = queue.popleft()
			if hd not in d:
				MIN = min(hd, MIN)
				d[hd] = curr.data
			if curr.left:
				queue.append([curr.left, hd - 1])
			if curr.right:
				queue.append([curr.right, hd + 1])
		while MIN in d:
			ans.append(d[MIN])
			MIN += 1
		return ans


class Solution:

	def topView(self, root):
		(que, res, hmap) = ([], [], {})
		que.append((root, 0))
		while que:
			(node, lvl) = que.pop(0)
			if lvl not in hmap:
				hmap[lvl] = node.data
			if node.left:
				que.append((node.left, lvl - 1))
			if node.right:
				que.append((node.right, lvl + 1))
		for i in sorted(hmap):
			res.append(hmap[i])
		return res


from collections import deque

class Solution:

	def topView(self, root):
		ans = []
		if root is None:
			return ans
		node_hd = {}
		q = deque()
		q.append([root, 0])
		while q:
			(node, level) = q.popleft()
			if level not in node_hd:
				node_hd[level] = node.data
			if node.left is not None:
				q.append((node.left, level - 1))
			if node.right is not None:
				q.append((node.right, level + 1))
		for val in sorted(node_hd.keys()):
			ans.append(node_hd[val])
		return ans


from collections import deque, defaultdict

class Solution:

	def topView(self, root):
		d = defaultdict(lambda : 0)
		ans = []
		if root is None:
			return
		leftmost = 0
		q = deque()
		q.append((root, 0))
		while q:
			top = q.popleft()
			(temp, ind) = top
			if ind not in d:
				d[ind] = temp.data
			leftmost = min(ind, leftmost)
			if temp.left:
				q.append((temp.left, ind - 1))
			if temp.right:
				q.append((temp.right, ind + 1))
		for i in range(leftmost, len(d)):
			if d[i]:
				ans.append(d[i])
		return ans


class Solution:

	def topView(self, root):
		dicto = {}
		queue = []
		queue.append([root, 0])

		def topViewUtil(node, level):
			nonlocal dicto
			while queue:
				element = queue.pop(0)
				level = element[1]
				if level not in dicto:
					dicto[level] = element[0].data
				if element[0].left:
					queue.append([element[0].left, level - 1])
				if element[0].right:
					queue.append([element[0].right, level + 1])
		topViewUtil(root, 0)
		(levels, elements) = ([], [])
		for (k, v) in dicto.items():
			levels.append(k)
			elements.append(v)
		return [y for (_, y) in sorted(zip(levels, elements))]


class Solution:

	def topView(self, root):
		if not root:
			return []
		queue = []
		queue.append([root, 0])
		seen = {}
		ret = []
		while queue:
			n = len(queue)
			for i in range(n):
				curr = queue.pop(0)
				if curr[1] not in seen.keys():
					seen[curr[1]] = curr[0].data
				if curr[0].left:
					queue.append([curr[0].left, curr[1] - 1])
				if curr[0].right:
					queue.append([curr[0].right, curr[1] + 1])
		val = seen.keys()
		val = sorted(val)
		for i in val:
			ret.append(seen[i])
		return ret


import sys

class Solution:

	def topView(self, root):
		q = []
		map = {}
		mini = sys.maxsize
		q.append((root, 0))
		while len(q) != 0:
			n = len(q)
			for i in range(n):
				(node, l) = q.pop(0)
				if l not in map:
					map[l] = node.data
				mini = min(mini, l)
				if node.left:
					q.append((node.left, l - 1))
				if node.right:
					q.append((node.right, l + 1))
		ans = []
		while mini in map:
			ans.append(map[mini])
			mini = mini + 1
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		ans = {}
		queue = deque([(root, 0)])
		while queue:
			(node, level) = queue.popleft()
			if not ans.get(level):
				ans[level] = node.data
			if node.left:
				queue.append((node.left, level - 1))
			if node.right:
				queue.append((node.right, level + 1))
		return [val for (_, val) in sorted(ans.items())]


class Solution:

	def func(self, e):
		return e[0]

	def dfs(self, root, dic, col, row):
		if root == None:
			return
		if col in dic:
			if row < dic[col][0]:
				dic[col] = (row, root.data)
		else:
			dic[col] = (row, root.data)
		self.dfs(root.left, dic, col - 1, row + 1)
		self.dfs(root.right, dic, col + 1, row + 1)

	def topView(self, root):
		dic = {}
		self.dfs(root, dic, 0, 0)
		result = []
		for i in sorted(dic):
			result.append(dic[i][1])
		return result


class Solution:

	def topView(self, root):
		dic = {}
		max1 = min1 = 0
		q = [[root, 0]]
		while q:
			(node, dist) = q.pop(0)
			if dist not in dic:
				dic[dist] = node.data
			if node.left:
				q.append([node.left, dist - 1])
			if node.right:
				q.append([node.right, dist + 1])
			min1 = min(min1, dist)
			max1 = max(max1, dist)
		ans = []
		for i in range(min1, max1 + 1):
			ans.append(dic[i])
		return ans


class Solution:

	def topView(self, root):
		res = []
		if root is None:
			return
		else:
			visit = {}
			q = []
			hd = 0
			q.append([root, hd])
			while len(q) != 0:
				(rn, hd) = q.pop(0)
				if hd not in visit:
					visit[hd] = [rn.data]
				else:
					visit[hd].append(rn.data)
				if rn.left is not None:
					q.append([rn.left, hd - 1])
				if rn.right is not None:
					q.append([rn.right, hd + 1])
			for i in sorted(visit.keys()):
				res.append(visit[i][0])
			return res


class Solution:

	def topView(self, root):
		if root == None:
			return []
		d = {}

		def fu(root, lvl=0, hd=0):
			if root == None:
				return
			if hd not in d or lvl < d[hd][0]:
				d[hd] = (lvl, root.data)
			fu(root.left, lvl + 1, hd - 1)
			fu(root.right, lvl + 1, hd + 1)
		fu(root)
		return [x[1] for (_, x) in sorted(d.items())]


class Solution:

	def topView(self, root):
		if not root:
			return []
		d = {}

		def traverse(node, hd, level):
			if not node:
				return
			if hd not in d or level < d[hd][1]:
				d[hd] = [node.data, level]
			traverse(node.left, hd - 1, level + 1)
			traverse(node.right, hd + 1, level + 1)
		traverse(root, 0, 0)
		return [x[0] for (_, x) in sorted(d.items())]


class Solution:

	def topView(self, root):
		if not root:
			return
		m = {}
		hd = 0
		q = []
		q.append((root, hd))
		(mn, mx) = (0, 0)
		while q:
			temp = q.pop(0)
			hd = temp[1]
			node = temp[0]
			if hd in m:
				m[hd].append(node.data)
			else:
				m[hd] = [node.data]
			if node.left:
				q.append((node.left, hd - 1))
			if node.right:
				q.append((node.right, hd + 1))
			if mn > hd:
				mn = hd
			elif mx < hd:
				mx = hd
		ans = []
		for i in range(mn, mx + 1):
			if i in m:
				tmp = m[i]
				ans.append(tmp[0])
		return ans


class Solution:

	def topView(self, root):
		queue = [[root, 0, 0]]
		res = {}
		while queue:
			fwd = []
			while queue:
				val = queue.pop(0)
				if val[0].left:
					fwd.append([val[0].left, val[1] + 1, val[2] - 1])
				if val[0].right:
					fwd.append([val[0].right, val[1] + 1, val[2] + 1])
				if val[2] not in res:
					res[val[2]] = val[0]
			queue = fwd
		ans = []
		for i in sorted(res.keys()):
			ans.append(res[i].data)
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		if not root:
			return
		result = []
		d = dict()
		queue = deque([(root, 0)])
		while queue:
			n = len(queue)
			(node, y) = queue.popleft()
			if y not in d:
				d[y] = node.data
			if node.left:
				queue.append((node.left, y - 1))
			if node.right:
				queue.append((node.right, y + 1))
		m = min(d)
		for i in range(m, m + len(d)):
			result.append(d[i])
		return result


from queue import Queue

class Solution:

	def topView(self, root):
		topnode = {}
		q = Queue()
		q.put((root, 0))
		while not q.empty():
			(node, tmp) = q.get()
			if tmp not in topnode.keys():
				topnode[tmp] = node.data
			if node.left:
				q.put((node.left, tmp - 1))
			if node.right:
				q.put((node.right, tmp + 1))
		ans = []
		for i in sorted(topnode.keys()):
			ans.append(topnode[i])
		return ans


class Solution:

	def topView(self, root):

		def traversal(root, x, y):
			if not root:
				return
			if y not in d:
				d[y] = (root.data, x)
			elif d[y][1] > x:
				d[y] = (root.data, x)
			traversal(root.left, x + 1, y - 1)
			traversal(root.right, x + 1, y + 1)
		result = []
		d = dict()
		traversal(root, 0, 0)
		m = min(d)
		for i in range(m, m + len(d)):
			result.append(d[i][0])
		return result


class Solution:

	def topView(self, root):
		d = {}
		q = [[root, 0]]
		while len(q) != 0:
			current = q[0][0]
			index = q[0][1]
			q.pop(0)
			if index in d:
				d[index].append(current.data)
			else:
				d[index] = [current.data]
			if current.left != None:
				q.append([current.left, index - 1])
			if current.right != None:
				q.append([current.right, index + 1])
		values = []
		for i in sorted(d.keys()):
			values.append(d[i])
		ans = []
		for i in values:
			ans.append(i[0])
		return ans


class Solution:

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

	def topView(self, root):
		q = deque()
		q.append([root, 0])
		while q:
			(v, x) = q.popleft()
			if not x in self.map:
				self.map[x] = v
			if v.left:
				q.append([v.left, x - 1])
			if v.right:
				q.append([v.right, x + 1])
		answer = []
		for i in sorted(self.map):
			answer.append(self.map[i].data)
		return answer


class Solution:

	def topView(self, root):
		hmap = {}
		Q = []
		lis = []
		Q.append([0, root])
		while len(Q) != 0:
			val = Q[0]
			dist = val[0]
			comp = val[1]
			if dist in hmap:
				pass
			else:
				hmap[dist] = comp.data
			Q.pop(0)
			if comp.left:
				Q.append([dist - 1, comp.left])
			if comp.right:
				Q.append([dist + 1, comp.right])
		sor = sorted(hmap)
		for i in sor:
			lis.append(hmap[i])
		return lis


class Solution:

	def topView(self, root):
		(x, y) = (0, 0)
		(l, r) = (0, 0)
		self.mapping = {}
		q = [(x, y, root)]
		while q:
			(x, y, front) = q.pop(0)
			if not self.mapping.get(x):
				self.mapping[x] = (y, front.data)
			(l, r) = (min(l, x), max(r, x))
			if front.left:
				q.append((x - 1, y + 1, front.left))
			if front.right:
				q.append((x + 1, y + 1, front.right))
		res = []
		while l <= r:
			res.append(self.mapping[l][1])
			l += 1
		return res


class Solution:

	def topView(self, root):
		ans = []

		def dfs(node, lvl, dis):
			if not node:
				return
			ans.append((node.data, lvl, dis))
			dfs(node.left, lvl + 1, dis - 1)
			dfs(node.right, lvl + 1, dis + 1)
		dfs(root, 0, 0)
		ans.sort(key=lambda x: x[1])
		ans.sort(key=lambda x: x[2])
		fans = []
		lastI = -float('inf')
		for n in ans:
			(cVa, clv, cdi) = n
			if cdi > lastI:
				fans.append(cVa)
				lastI = cdi
		return fans


from collections import defaultdict

class Solution:

	def topView(self, root):
		queue = []
		my_dict = defaultdict(list)
		queue.append([root, 0, 0])
		while queue:
			curr = queue[0][0]
			level = queue[0][1]
			vertical = queue[0][2]
			queue.pop(0)
			my_dict[vertical].append([curr.data, level])
			if curr.left:
				queue.append([curr.left, level + 1, vertical - 1])
			if curr.right:
				queue.append([curr.right, level + 1, vertical + 1])
		ans = []
		for i in sorted(my_dict.keys()):
			ans.append(my_dict[i][0][0])
		return ans


from queue import Queue

class Solution:

	def topView(self, root):
		if not root:
			return []
		q = Queue()
		arr = []
		ans = []
		map = {}
		q.put([0, root])
		while not q.empty():
			(a, b) = q.get()
			if a not in map:
				map[a] = b.data
			if b.left:
				q.put([a - 1, b.left])
			if b.right:
				q.put([a + 1, b.right])
		for a in map:
			arr.append([a, map[a]])
		arr.sort()
		for a in arr:
			ans.append(a[1])
		return ans


class Solution:

	def topView(self, root):

		def top(root, level):
			q = deque()
			q.append((0, root))
			d = {}
			while q:
				for i in range(len(q)):
					(level, node) = q.popleft()
					if level not in d:
						d[level] = node.data
					if node.left:
						q.append((level - 1, node.left))
					if node.right:
						q.append((level + 1, node.right))
			return d
		le = float('inf')
		r = float('-inf')
		d = top(root, 0)
		for i in d:
			le = min(le, i)
			r = max(r, i)
		res = []
		for i in range(le, r + 1):
			res.append(d[i])
		return res


class Solution:

	def topView(self, root):
		res = []
		q = []
		d = {}
		if root == None:
			return []
		q.append((root, 0))
		while q:
			l = len(q)
			for i in range(l):
				(x, y) = q.pop(0)
				if y not in d:
					d[y] = x.data
				if x != None and x.left != None:
					q.append((x.left, y - 1))
				if x != None and x.right != None:
					q.append((x.right, y + 1))
		for v in sorted(d.keys()):
			res.append(d[v])
		return res


class Solution:

	def rec_sol_left(self, root, dist, max_dist, ans):
		if dist > max_dist[0]:
			ans.append(root.data)
			max_dist[0] = dist
		if root.left != None:
			self.rec_sol_left(root.left, dist + 1, max_dist, ans)
		if root.right != None:
			self.rec_sol_left(root.right, dist - 1, max_dist, ans)
		return

	def rec_sol_right(self, root, dist, max_dist, ans):
		if dist > max_dist[0]:
			ans.append(root.data)
			max_dist[0] = dist
		if root.right != None:
			self.rec_sol_right(root.right, dist + 1, max_dist, ans)
		if root.left != None:
			self.rec_sol_right(root.left, dist - 1, max_dist, ans)
		return

	def topView(self, root):
		queue = []
		mp = {}
		mp[0] = root.data
		queue.append([root, 0])
		while len(queue) != 0:
			temp = queue.pop(0)
			(temp_node, temp_dist) = (temp[0], temp[1])
			if temp_dist not in list(mp.keys()):
				mp[temp_dist] = temp_node.data
			if temp_node.left != None:
				queue.append([temp_node.left, temp_dist - 1])
			if temp_node.right != None:
				queue.append([temp_node.right, temp_dist + 1])
		final = []
		keys = list(mp.keys())
		keys.sort()
		for k in keys:
			final.append(mp[k])
		return final
		ans = []
		max_dist = [-1]
		self.rec_sol_left(root, 0, max_dist, ans)
		ans.reverse()
		ans.pop()
		max_dist = [-1]
		self.rec_sol_right(root, 0, max_dist, ans)
		return ans


class Solution:

	def topView(self, root):
		res = []
		d = {}
		queue = []
		queue.append([root, 0])
		while queue != []:
			(root, level) = queue.pop()
			if level not in d:
				d[level] = [root.data]
			else:
				d[level].append(root.data)
			if root.left:
				queue.insert(0, [root.left, level - 1])
			if root.right:
				queue.insert(0, [root.right, level + 1])
		for ele in sorted(d):
			res.append(d[ele][0])
		return res


class Solution:

	def topView(self, root):
		res = []
		d = dict()
		custom_queue = []
		custom_queue.append([0, root])
		while custom_queue:
			temp = custom_queue.pop()
			(idx, parent) = temp
			if idx not in d:
				d[idx] = parent.data
			if parent.left:
				custom_queue.insert(0, [idx - 1, parent.left])
			if parent.right:
				custom_queue.insert(0, [idx + 1, parent.right])
		for ele in sorted(d):
			res.append(d[ele])
		return res


class Solution:

	def topView(self, root):
		mp = {}

		def util(root, x, y, map):
			if root:
				util(root.left, x - 1, y + 1, map)
				if x in map and map[x][1] > y or x not in map:
					map[x] = (root.data, y)
				util(root.right, x + 1, y + 1, map)
		util(root, 0, 0, mp)
		return [mp[keys][0] for keys in sorted(mp.keys())]


class Solution:

	def topView(self, root):
		nodes = {}

		def dfs(root, depth, pos):
			if not root:
				return
			if pos not in nodes:
				nodes[pos] = (root.data, depth)
			elif nodes[pos][1] > depth:
				nodes[pos] = (root.data, depth)
			dfs(root.left, depth + 1, pos - 1)
			dfs(root.right, depth + 1, pos + 1)
		dfs(root, 0, 0)
		return [nodes[i][0] for i in sorted(nodes)]


import collections

class Solution:

	def topView(self, root):
		res = []
		if root is None:
			return res
		queue = []
		m = {}
		hd_node = {}
		queue.append(root)
		hd_node[root] = 0
		m[0] = [root.data]
		while len(queue) > 0:
			temp = queue.pop(0)
			if temp.left:
				queue.append(temp.left)
				hd_node[temp.left] = hd_node[temp] - 1
				hd = hd_node[temp.left]
				if m.get(hd) is None:
					m[hd] = []
				m[hd].append(temp.left.data)
			if temp.right:
				queue.append(temp.right)
				hd_node[temp.right] = hd_node[temp] + 1
				hd = hd_node[temp.right]
				if m.get(hd) is None:
					m[hd] = []
				m[hd].append(temp.right.data)
		sorted_m = collections.OrderedDict(sorted(m.items()))
		for i in sorted_m.values():
			for j in i:
				res.append(j)
				break
		return res


class Solution:

	def topView(self, root):
		ans = []
		dic = {}
		if root is None:
			return ans
		queue = []
		queue.append([root, 0])
		while queue:
			elem = queue.pop(0)
			node = elem[0]
			line = elem[-1]
			if dic.get(line, -1) == -1:
				dic[line] = node.data
			if node.left is not None:
				queue.append([node.left, line - 1])
			if node.right is not None:
				queue.append([node.right, line + 1])
		key = dic.keys()
		for i in sorted(key):
			ans.append(dic[i])
		return ans


class Solution:

	def topView(self, root):
		q = [(0, root)]
		dict = {}
		list1 = []
		while q:
			node = q.pop(0)
			list1.append(node)
			if node[0] not in dict:
				dict[node[0]] = node[1].data
			if node[1].left is not None:
				q.append((node[0] - 1, node[1].left))
			if node[1].right is not None:
				q.append((node[0] + 1, node[1].right))
		k = sorted(dict.items(), key=lambda x: x[0])
		list2 = []
		for i in k:
			list2.append(i[1])
		return list2


class Solution:

	def topView(self, root):
		if not root:
			return []
		q = [[root, 0]]
		topview = {}
		while q:
			(node, level) = q.pop(0)
			if level not in topview:
				topview[level] = node.data
			if node.left:
				q.append([node.left, level - 1])
			if node.right:
				q.append([node.right, level + 1])
		return [topview[level] for level in sorted(topview.keys())]


class Solution:

	def topView(self, root):
		if root == None:
			return None
		dict = {}
		q1 = []
		q = []
		q1.append(root)
		q.append(0)
		while len(q1) > 0:
			curr = q1.pop(0)
			hd = q.pop(0)
			if hd not in dict:
				dict[hd] = curr.data
			if curr.left != None:
				q1.append(curr.left)
				q.append(hd - 1)
			if curr.right != None:
				q1.append(curr.right)
				q.append(hd + 1)
		arr = []
		for i in sorted(dict.keys()):
			arr.append(dict[i])
		return arr


from collections import deque

class Solution:

	def topView(self, root):
		que = deque([(root, 0)])
		(dct, res) = ({}, [])
		while que:
			(node, col) = que.popleft()
			if col not in dct:
				dct[col] = node.data
			if node.left:
				que.append((node.left, col - 1))
			if node.right:
				que.append((node.right, col + 1))
		cols = list(dct)
		cols.sort()
		for col in cols:
			res.append(dct[col])
		return res


from collections import deque

class Solution:

	def topView(self, root):
		q = deque([[0, root], None])
		ans = {}
		while q:
			curr = q.popleft()
			if not curr:
				if not q:
					return [ans[key] for key in sorted(ans)]
				else:
					q.append(None)
			else:
				dis = curr[0]
				node = curr[1]
				if dis not in ans:
					ans[dis] = node.data
				if node.left:
					q.append([dis - 1, node.left])
				if node.right:
					q.append([dis + 1, node.right])


from collections import defaultdict

class Solution:

	def topView(self, root):
		topView = []
		hash_map = defaultdict()
		dummy_node = (root, 0)
		queue = []
		queue.append(dummy_node)
		while queue:
			(node, x_cord) = queue.pop(0)
			if x_cord not in hash_map.keys():
				hash_map[x_cord] = node.data
			if node.left:
				queue.append((node.left, x_cord - 1))
			if node.right:
				queue.append((node.right, x_cord + 1))
		for i in sorted(hash_map.keys()):
			topView.append(hash_map[i])
		return topView


class Solution:

	def topView(self, root):
		ans = []
		q = []
		q.append([root, 0, 0])
		d = {}
		while q:
			(node, pos, lev) = q.pop(0)
			if pos not in d.keys():
				d[pos] = node.data
			if node.left:
				q.append([node.left, pos - 1, lev + 1])
			if node.right:
				q.append([node.right, pos + 1, lev + 1])
		for i in sorted(d):
			ans.append(d[i])
		return ans


from collections import defaultdict

class Solution:

	def topView(self, root):
		left = []
		right = []
		if not root:
			return []
		qu = deque([(root, 0, 0)])
		d = defaultdict(list)
		while qu:
			n = len(qu)
			for i in range(n):
				(curr, r, c) = qu.popleft()
				d[c].append(curr.data)
				if curr.left:
					qu.append((curr.left, r + 1, c - 1))
				if curr.right:
					qu.append((curr.right, r + 1, c + 1))
		ans = []
		for i in sorted(d.keys()):
			ans.append(d[i][0])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		has = {}
		q = deque()
		q.append(root)
		hd = 0
		root.hd = hd
		(min_hd, max_hd) = (0, 0)
		while q:
			temp = q.popleft()
			hd = temp.hd
			if hd not in has:
				has[hd] = temp.data
			max_hd = max(max_hd, hd)
			min_hd = min(min_hd, hd)
			if temp.left:
				temp.left.hd = hd - 1
				q.append(temp.left)
			if temp.right:
				temp.right.hd = hd + 1
				q.append(temp.right)
		res = []
		for i in range(min_hd, max_hd + 1):
			res.append(has[i])
		return res


class Pair:

	def __init__(self, node, hd):
		self.node = node
		self.hd = hd
from collections import deque

class Solution:

	def topView(self, root):
		if root == None:
			return []
		ans = []
		q = deque()
		dct = {}
		q.append(Pair(root, 0))
		while q:
			temp = q.popleft()
			cur = temp.node
			hd = temp.hd
			if hd in dct:
				pass
			else:
				dct[hd] = cur.data
			if cur.left:
				q.append(Pair(cur.left, hd - 1))
			if cur.right:
				q.append(Pair(cur.right, hd + 1))
		for hd in sorted(dct.keys()):
			ans.append(dct[hd])
		return ans


class Solution:

	def topView(self, root):
		dict = {}
		queue = deque()
		queue.append((root, 0))
		while queue:
			(curr, hd) = queue.popleft()
			if hd not in dict:
				dict[hd] = curr.data
			if curr.left:
				queue.append((curr.left, hd - 1))
			if curr.right:
				queue.append((curr.right, hd + 1))
		list1 = []
		for key in sorted(dict.keys()):
			list1.append(dict[key])
		return list1


class Solution:

	class point:
		x = None
		y = None

		def __init__(self, x, y):
			self.x = x
			self.y = y

	def topView(self, root):
		q = list()
		dct = dict()
		q.append(self.point(root, 0))
		while q:
			k = q.pop(0)
			x1 = k.x
			y1 = k.y
			if y1 in dct:
				dct[y1].append(x1.data)
			else:
				dct[y1] = list()
				dct[y1].append(x1.data)
			if x1.left != None:
				q.append(self.point(x1.left, y1 - 1))
			if x1.right != None:
				q.append(self.point(x1.right, y1 + 1))
		l1 = list(dct.keys())
		l1.sort()
		r = list()
		for i in l1:
			r.append(dct[i][0])
		return r


class Solution:

	def topView(self, root):
		my_map = {}

		def topView(root, dist, level):
			if root == None:
				return
			if dist not in my_map or level < my_map[dist][1]:
				my_map[dist] = (root.data, level)
			topView(root.left, dist - 1, level + 1)
			topView(root.right, dist + 1, level + 1)
		ans = []
		topView(root, 0, 0)
		for key in sorted(my_map.keys()):
			ans.append(my_map.get(key)[0])
		return ans


class Solution:

	def topView(self, root):
		ans = []
		queue = []
		mapp = {}
		if root is None:
			return ans
		queue.append((root, 0))
		while queue:
			element = queue.pop(0)
			node = element[0]
			level = element[1]
			if level not in mapp:
				mapp[level] = node.data
			if node.left is not None:
				queue.append((node.left, level - 1))
			if node.right is not None:
				queue.append((node.right, level + 1))
		for (key, val) in sorted(mapp.items()):
			ans.append(val)
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		result = []
		q = deque()
		linemap = {}
		q.append((root, 0))
		while q:
			ele = q.popleft()
			node = ele[0]
			line = ele[1]
			if line not in linemap:
				linemap[line] = node.data
			if node.left is not None:
				q.append((node.left, line - 1))
			if node.right is not None:
				q.append((node.right, line + 1))
		for key in sorted(linemap.keys()):
			result.append(linemap[key])
		return result


class Solution:

	def topView(self, root):
		ans = []
		if root is None:
			return ans
		(mpp, q) = (dict(), list())
		q.append((root, 0))
		while q:
			ele = q[0]
			q.pop(0)
			node = ele[0]
			line = ele[1]
			if line not in mpp:
				mpp[line] = node.data
			if node.left:
				q.append((node.left, line - 1))
			if node.right:
				q.append((node.right, line + 1))
		for ele in sorted(mpp.keys()):
			ans.append(mpp[ele])
		return ans


from collections import deque

class Solution:

	def topView(self, root):
		distance_val_map = {}
		res = []
		if not root:
			return []
		queue = deque([(root, 0)])
		while queue:
			for i in range(len(queue)):
				(node, distance) = queue.popleft()
				if distance not in distance_val_map:
					distance_val_map[distance] = node.data
				if node.left:
					queue.append((node.left, distance - 1))
				if node.right:
					queue.append((node.right, distance + 1))
		sorted_keys = sorted(distance_val_map.keys())
		for key in sorted_keys:
			res.append(distance_val_map[key])
		return res


from collections import deque
from collections import defaultdict

class Solution:

	def topView(self, root):
		orderMap = defaultdict(list)
		result = []
		if not root:
			return result
		queue = deque()
		queue.append((root, 0))
		while queue:
			for i in range(len(queue)):
				(currentNode, order) = queue.popleft()
				orderMap[order].append(currentNode.data)
				if currentNode.left:
					queue.append((currentNode.left, order - 1))
				if currentNode.right:
					queue.append((currentNode.right, order + 1))
		for key in sorted(orderMap.keys()):
			result.append(orderMap[key][0])
		return result