Given a binary tree, print the bottom view from left to right.
A node is included in bottom view if it can be seen when we look at the tree from bottom.
                      20
                    /    \
                  8       22
                /   \        \
              5      3       25
                    /   \      
                  10    14
For the above tree, the bottom view is 5 10 3 14 25.
If there are multiple bottom-most nodes for a horizontal distance from root, then print the later one in level traversal. For example, in the below diagram, 3 and 4 are both the bottommost nodes at horizontal distance 0, we need to print 4.
                      20
                    /    \
                  8       22
                /   \     /   \
              5      3 4     25
                     /    \      
                 10       14
For the above tree the output should be 5 10 4 14 25.
Note: The Input/Output format and Example given are used for the system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from the stdin/console. The task is to complete the function specified, and not to write the full code.
 
Example 1:
Input:
       1
     /   \
    3     2
Output: 3 1 2
Explanation:
First case represents a tree with 3 nodes
and 2 edges where root is 1, left child of
1 is 3 and right child of 1 is 2.
Thus nodes of the binary tree will be
printed as such 3 1 2.
Example 2:
Input:
         10
       /    \
      20    30
     /  \
    40   60
Output: 40 20 60 30
Your Task:
This is a functional problem, you don't need to care about input, just complete the function bottomView() which takes the root node of the tree as input and returns an array containing the bottom view of the given tree.
Expected Time Complexity: O(N*logN).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def bottomView(self, root):

        # code here

Solutions:
from collections import defaultdict

class Solution:

	def bottomView(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(), reverse=True):
			if k[0] not in i:
				i[k[0]] = 1
				x.append(v[-1])
		x.reverse()
		return x


class Solution:

	def bottomView(self, root):

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


from collections import OrderedDict

class Solution:

	def bottomView(self, root):
		queue = [[root, 0]]
		ans = defaultdict(int)
		while queue:
			size = len(queue)
			for i in range(size):
				(curr, hd) = queue.pop(0)
				ans[hd] = curr.data
				if curr.left != None:
					queue.append([curr.left, hd - 1])
				if curr.right != None:
					queue.append([curr.right, hd + 1])
		ans = OrderedDict(sorted(ans.items()))
		return ans.values()


class Solution:

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


class Solution:

	def bottomView(self, root):
		d = {}
		levels = []
		q = []
		q.append(root)
		levels.append(0)
		while q:
			curr = q.pop(0)
			level = levels.pop(0)
			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)
		res = []
		for i in sorted(d.keys()):
			res.append(d[i])
		return res


from collections import deque

class Solution:

	def bottomView(self, root):
		if not root:
			return []
		d = {}
		q = deque([(root, 0)])
		while q:
			(x, l) = q.popleft()
			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 bottomView(self, root):
		if root == None:
			return []
		q = [(root, 0)]
		d = dict()
		while q:
			(nod, h) = q.pop(0)
			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 solve(self, root):
		ans = []
		if root is None:
			return ans
		queue = []
		queue.append([root, 0])
		d = {}
		while queue != []:
			temp = queue.pop(0)
			if temp[0].left is not None:
				queue.append([temp[0].left, temp[1] - 1])
			if temp[0].right is not None:
				queue.append([temp[0].right, temp[1] + 1])
			d[temp[1]] = temp[0].data
		for ele in sorted(d.keys()):
			ans.append(d[ele])
		return ans

	def bottomView(self, root):
		res = self.solve(root)
		return res


class Solution:

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


from collections import deque

class Solution:

	def bottomView(self, root):
		if root is None:
			return []
		queue = deque()
		ans = {}
		queue.append((root, 0))
		(minb, maxb) = (0, 0)
		while len(queue) != 0:
			size = len(queue)
			for i in range(size):
				(node, index) = queue[0]
				minb = min(minb, index)
				maxb = max(maxb, index)
				queue.popleft()
				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 bottomView(self, root):
		ans = []
		queue = deque([(root, 0)])
		views = {}
		min_pos = max_pos = 0
		while queue:
			(node, pos) = queue.popleft()
			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 bottomView(self, root):
		myMap = {}
		queue = deque([(root, 0)])
		while queue:
			(node, hd) = queue.popleft()
			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 bottomView(self, root):
		hd = 0
		root.hd = hd
		q = []
		q.append(root)
		d = {}
		(min_hd, max_hd) = (0, 0)
		res = []
		while len(q) > 0:
			curr_node = q.pop(0)
			hd = curr_node.hd
			min_hd = min(min_hd, hd)
			max_hd = max(max_hd, hd)
			d[hd] = curr_node.data
			if curr_node.left:
				curr_node.left.hd = hd - 1
				q.append(curr_node.left)
			if curr_node.right:
				curr_node.right.hd = hd + 1
				q.append(curr_node.right)
		for i in range(min_hd, max_hd + 1):
			res.append(d[i])
		return res


class Solution:

	def bottomView(self, root):
		dicto = {}
		stack = []
		if root:
			stack.append([root, 0])
		while stack:
			element = stack.pop(0)
			level = element[1]
			dicto[level] = element[0].data
			if element[0].left:
				stack.append([element[0].left, level - 1])
			if element[0].right:
				stack.append([element[0].right, level + 1])
		return [dicto[k] for k in sorted(dicto)]


from collections import deque

class Solution:

	def bottomView(self, root):
		q = deque([[root, 0]])
		d = {}
		while q:
			(node, line) = q.popleft()
			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


class Solution:

	def bottomView(self, root):
		store = {}
		queue = []
		queue.append((root, 0))
		while queue:
			(node, line) = queue.pop(0)
			if line not in store:
				store[line] = node.data
			else:
				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, value) in sorted(store.items()):
			res.append(value)
		return res


class Solution:

	def bottomView(self, root):
		queue = [(root, 0)]
		temp = {0: root.data}
		while queue:
			(node, level) = queue.pop(0)
			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 bottomView(self, root):
		X = {}
		queue = deque()
		queue.append([root, 0])
		while queue:
			(node, x) = queue.popleft()
			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 bottomView(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)
			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 bottomView(self, root):
		queue = [(0, 0, root)]
		levelElements = {}
		while queue:
			(col, row, node) = queue.pop(0)
			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]


class Solution:

	def bottomView(self, root):
		if not root:
			return []
		que = deque()
		que.append((0, root))
		dic = {}
		while len(que) != 0:
			(col, temp) = que.popleft()
			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 bottomView(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
			else:
				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


class Solution:

	def bottomView(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]
			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 bottomView(self, root):
		(que, res, hmap) = ([], [], {})
		que.append((root, 0))
		while que:
			(node, lvl) = que.pop(0)
			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 bottomView(self, root):
		ans = []
		if root is None:
			return ans
		mpp = {}
		q = deque()
		q.append((root, 0))
		while q:
			(node, line) = q.popleft()
			mpp[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 val in sorted(mpp.keys()):
			ans.append(mpp[val])
		return ans


class Solution:

	def bottomView(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
			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


from collections import defaultdict, deque

class Tree:

	def __init__(self, node, idx):
		self.node = node
		self.index = idx

class Solution:

	def bottomView(self, root):
		if not root:
			return []
		map = defaultdict(list)
		queue = deque()
		queue.append(Tree(root, 0))
		while len(queue):
			size = len(queue)
			while size:
				curr_node = queue.popleft()
				map[curr_node.index].append(curr_node.node.data)
				if curr_node.node.left:
					queue.append(Tree(curr_node.node.left, curr_node.index - 1))
				if curr_node.node.right:
					queue.append(Tree(curr_node.node.right, curr_node.index + 1))
				size = size - 1
		keys = sorted(map.keys())
		ans = []
		for key in keys:
			ans.append(map[key][-1])
		return ans


class Solution:

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


class Solution:

	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 bottomView(self, root):
		dic = {}
		self.dfs(root, dic, 0, 0)
		result = []
		for i in sorted(dic):
			result.append(dic[i][1])
		return result


import sys

class Solution:

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


class Solution:

	def bottomView(self, root):
		if root is None:
			return
		else:
			visit = {}
			q = deque()
			hd = 0
			q.append([root, hd])
			while len(q) != 0:
				(rn, hd) = q.popleft()
				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])
			res = []
			for i in sorted(visit.keys()):
				res.append(visit[i][-1])
			return res


class Solution:

	def bottomView(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[-1])
		return ans


class Solution:

	def bottomView(self, root):
		res = {}
		queue = [[root, 0, 0]]
		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] in res:
					res[val[2]].append(val[0].data)
				else:
					res[val[2]] = [val[0].data]
			queue = fwd
		ans = []
		for i in sorted(res.keys()):
			ans.append(res[i].pop())
		return ans


from collections import deque

class Solution:

	def bottomView(self, root):
		if not root:
			return []
		result = []
		d = dict()
		queue = deque([(root, 0)])
		while queue:
			(node, y) = queue.popleft()
			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


class Solution:

	def bottomView(self, root):

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


class Solution:

	def bottomView(self, root):
		hashmap = dict()
		queue = [(root, 0)]
		while queue:
			(node, level) = queue.pop(0)
			hashmap[level] = node.data
			if node.left:
				queue.append((node.left, level - 1))
			if node.right:
				queue.append((node.right, level + 1))
		ans = list()
		for key in sorted(hashmap.keys()):
			ans.append(hashmap[key])
		return ans


class Solution:

	def bottomView(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[-1])
		return ans


class Solution:

	def findbootomview(self, root, dic, horizontal, level, minl, a):
		if root == None:
			return
		if dic[horizontal + minl] <= level:
			dic[horizontal + minl] = level
			a[horizontal + minl] = root.data
		self.findbootomview(root.left, dic, horizontal - 1, level + 1, minl, a)
		self.findbootomview(root.right, dic, horizontal + 1, level + 1, minl, a)

	def findhrztl(self, root, hl):
		if root == None:
			return
		global minl
		global maxl
		if minl > hl:
			minl = hl
		if maxl < hl:
			maxl = hl
		self.findhrztl(root.left, hl - 1)
		self.findhrztl(root.right, hl + 1)

	def bottomView(self, root):
		global minl
		global maxl
		(minl, maxl) = (100000, -100000)
		self.findhrztl(root, 0)
		dic = list()
		for i in range(abs(minl) + maxl + 1):
			dic.append(-1)
		a = [0] * (abs(minl) + maxl + 1)
		self.findbootomview(root, dic, 0, 0, abs(minl), a)
		dic = list()
		return a


class Solution:

	def bottomView(self, root):
		hmap = {}
		Q = []
		lis = []
		Q.append([0, root])
		while len(Q) != 0:
			val = Q[0]
			dist = val[0]
			comp = val[1]
			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


from collections import OrderedDict

class Solution:

	def bottomView(self, root):
		if root is None:
			return []
		bottomView = []
		q = deque()
		q.append([root, 0])
		viewMap = {}
		while q:
			for i in range(len(q)):
				(currentNode, position) = q.popleft()
				viewMap[position] = currentNode.data
				if currentNode.left is not None:
					q.append([currentNode.left, position - 1])
				if currentNode.right is not None:
					q.append([currentNode.right, position + 1])
		sortedViewMap = OrderedDict(sorted(viewMap.items()))
		for (key, val) in sortedViewMap.items():
			bottomView.append(val)
		return bottomView


from collections import deque

class Solution:

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

	def bottomView(self, root):
		q = deque()
		q.append([root, 0])
		while q:
			(v, x) = q.popleft()
			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 bottomView(self, root):
		d = {}
		q = deque()
		q.append((root, 0))
		while q:
			(node, dist) = q.popleft()
			d.setdefault(dist, []).append(node.data)
			if node.left:
				q.append((node.left, dist - 1))
			if node.right:
				q.append((node.right, dist + 1))
		m = []
		for key in sorted(d.keys()):
			m.append(d[key][-1])
		t = []
		for i in m:
			t.append(i)
		return t


class Solution:

	def bottomView(self, root):
		(l, r) = (0, 0)
		mapping = {}
		(x, y) = (0, 0)
		q = [(x, y, root)]
		while q:
			(x, y, front) = q.pop(0)
			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(mapping[l][1])
			l += 1
		return res


from collections import deque

class Solution:

	def bottomView(self, root):
		minvalue = maxvalue = 0
		dictset = dict()
		dQ = deque()
		dQ.append([root, 0])
		while dQ:
			times = len(dQ)
			for i in range(times):
				(havenode, level) = dQ.popleft()
				dictset[level] = havenode.data
				minvalue = min(minvalue, level)
				maxvalue = max(maxvalue, level)
				if havenode.left != None:
					dQ.append([havenode.left, level - 1])
				if havenode.right != None:
					dQ.append([havenode.right, level + 1])
		resultentdataset = list()
		for key in range(minvalue, maxvalue + 1):
			resultentdataset.append(dictset[key])
		return resultentdataset


class Solution:

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

		def dfs(node, lvl, dis):
			if not node:
				return
			ans.append((node.data, lvl, dis))
			dfs(node.right, lvl + 1, dis + 1)
			dfs(node.left, 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


class Solution:

	def bottomView(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][-1][0])
		return ans


from collections import deque

class Solution:

	def bottomView(self, root):

		def dfs(node, pos):
			if node == None:
				return (pos, pos)
			(l1, r1) = dfs(node.left, pos - 1)
			(l2, r2) = dfs(node.right, pos + 1)
			return (min(l1, l2), max(r1, r2))
		(mn, mx) = dfs(root, 0)
		mn += 1
		mx -= 1
		arr = [0 for _ in range(mx - mn + 1)]
		q = deque()
		q.append((root, 0))
		while q:
			(cur, pos) = q.popleft()
			if cur == None:
				continue
			arr[pos - mn] = cur.data
			q.append((cur.left, pos - 1))
			q.append((cur.right, pos + 1))
		return arr


from queue import Queue

class Solution:

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


class Solution:

	def bottomView(self, root):
		h = {}

		def writer(nd: Node, ind: int, depth: int):
			if ind in h:
				(dat, old_depth) = h[ind]
				if depth >= old_depth:
					h[ind] = (nd.data, depth)
			else:
				h[ind] = (nd.data, depth)
			if nd.left:
				writer(nd.left, ind - 1, depth + 1)
			if nd.right:
				writer(nd.right, ind + 1, depth + 1)
		writer(root, 0, 0)
		start = min(h)
		ending = max(h)
		store = []
		for i in range(start, ending + 1):
			store.append(h[i][0])
		return store


class Solution:

	def bottomView(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][-1])
		return res


class Solution:

	def bottomView(self, root):

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


import collections

class Solution:

	def bottomView(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():
			res.append(i[-1])
		return res


class Solution:

	def bottomView(self, root):
		ans = []
		if root is None:
			return ans
		q = [[root, 0]]
		dic = {}
		while q:
			elem = q.pop(0)
			node = elem[0]
			line = elem[-1]
			dic[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])
		key = dic.keys()
		for i in sorted(key):
			ans.append(dic[i])
		return ans


class Solution:

	def bottomView(self, root):
		q = [(0, root)]
		dict = {}
		list1 = []
		while q:
			node = q.pop(0)
			list1.append(node)
			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 bottomView(self, root):
		if not root:
			return []
		hd_map = {}
		q = deque([(root, 0)])
		while q:
			(node, hd) = q.popleft()
			hd_map[hd] = node.data
			if node.left:
				q.append((node.left, hd - 1))
			if node.right:
				q.append((node.right, hd + 1))
		return [hd_map[hd] for hd in sorted(hd_map)]


class Solution:

	def bottomView(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)
			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


class Solution:

	def bottomView(self, root):

		def find_val(root, h, level, d):
			if root:
				if d.get(h, -1) == -1 or level >= d[h][0]:
					d[h] = [level, root.data]
				level += 1
				find_val(root.left, h - 1, level, d)
				find_val(root.right, h + 1, level, d)
		d = {}
		find_val(root, 0, 0, d)
		res = [[key, d[key][1]] for key in d]
		res.sort()
		return [i[1] for i in res]


from collections import deque

class Solution:

	def bottomView(self, root):
		que = deque([(root, 0)])
		(dct, res) = ({}, [])
		while que:
			(node, col) = que.popleft()
			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


class Solution:

	def bottomView(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]
				ans[dis] = node.data
				if node.left:
					q.append([dis - 1, node.left])
				if node.right:
					q.append([dis + 1, node.right])


class Solution:

	def bottomView(self, root):
		bottomView = []
		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
			else:
				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()):
			bottomView.append(hash_map[i])
		return bottomView


class Solution:

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


from collections import deque

class Solution:

	def bottomView(self, root):
		has = {}
		hd = 0
		root.hd = hd
		q = deque()
		q.append(root)
		(max_hd, min_hd) = (0, 0)
		while q:
			temp = q.popleft()
			hd = temp.hd
			max_hd = max(max_hd, hd)
			min_hd = min(min_hd, hd)
			has[hd] = temp.data
			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 Solution:

	def bottomView(self, root):
		q = [[root, 0]]
		hs = {0: root.data}
		while len(q):
			n = len(q)
			for i in range(n):
				k = q.pop(0)
				hs[k[1]] = k[0].data
				if k[0].left:
					q.append([k[0].left, k[1] - 1])
				if k[0].right:
					q.append([k[0].right, k[1] + 1])
		z = min(hs.keys())
		x = []
		while z in hs:
			x.append(hs[z])
			z += 1
		return x


class Pair:

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

class Solution:

	def bottomView(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:
				dct[hd] = cur.data
			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 bottomView(self, root):
		dict = {}
		queue = deque()
		queue.append((root, 0))
		while queue:
			(curr, hd) = queue.popleft()
			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:

	def rec_sol(self, root, ans, dist):
		ans[dist] = root.data
		if root.left != None:
			self.rec_sol(root.left, ans, dist - 1)
		if root.right != None:
			self.rec_sol(root.right, ans, dist + 1)
		return

	def bottomView(self, root):
		ans = {}
		queue = []
		queue.append([root, 0])
		while len(queue) != 0:
			curr = queue.pop(0)
			(curr_node, curr_dist) = (curr[0], curr[1])
			ans[curr_dist] = curr_node.data
			if curr_node.left != None:
				queue.append([curr_node.left, curr_dist - 1])
			if curr_node.right != None:
				queue.append([curr_node.right, curr_dist + 1])
		sort_keys = list(ans.keys())
		sort_keys.sort()
		final = []
		for key in sort_keys:
			final.append(ans[key])
		return final


class Solution:

	def bottomView(self, root):
		if root is None:
			return []
		q = []
		q.append((root, 0))
		xMap = {}
		while len(q) > 0:
			(node, dir) = q.pop(0)
			xMap[dir] = node.data
			if node.left:
				q.append((node.left, dir - 1))
			if node.right:
				q.append((node.right, dir + 1))
		lst = list(xMap.keys())
		lst.sort()
		for ind in range(len(lst)):
			lst[ind] = xMap[lst[ind]]
		return lst


from collections import deque, OrderedDict

class Solution:

	def bottomView(self, root):
		queue = deque()
		map = {}
		vertical = 0
		curr = root
		queue.append([curr, vertical])
		while len(queue) != 0:
			(curr, vertical) = queue.popleft()
			map[vertical] = curr.data
			if curr.left:
				queue.append([curr.left, vertical - 1])
			if curr.right:
				queue.append([curr.right, vertical + 1])
		ans = []
		for i in sorted(map.keys()):
			ans.append(map[i])
		return ans


class Solution:

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

		def bottomView(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)
			bottomView(root.left, dist - 1, level + 1)
			bottomView(root.right, dist + 1, level + 1)
		ans = []
		bottomView(root, 0, 0)
		for key in sorted(my_map.keys()):
			ans.append(my_map.get(key)[0])
		return ans


class Solution:

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


class Solution:

	def bottomView(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]
			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 OrderedDict

class Solution:

	def bottomView(self, root):
		ans = []
		if not root:
			return ans
		(mpp, q) = (OrderedDict(), [])
		q.append((root, 0))
		while q:
			ele = q[0]
			q.pop(0)
			node = ele[0]
			line = ele[1]
			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


class Solution:

	def bottomView(self, root):
		if not root:
			return []
		traversal = defaultdict(list)
		queue = [(root, 0)]
		while queue:
			(node, pos) = queue.pop(0)
			traversal[pos].append(node.data)
			if node.left:
				queue.append((node.left, pos - 1))
			if node.right:
				queue.append((node.right, pos + 1))
		result = []
		for key in sorted(traversal):
			result.append(traversal[key])
		return [item[-1] for item in result]


class Solution:

	def bottomView(self, root):
		d = {}
		q = []
		q.append([root, 0])
		while len(q) != 0:
			node = q[0][0]
			val = q[0][1]
			if val in d.keys():
				d[val].append(node.data)
			else:
				d[val] = [node.data]
			if node.left:
				q.append([node.left, val - 1])
			if node.right:
				q.append([node.right, val + 1])
			q.pop(0)
		t = []
		for i in sorted(d.keys()):
			t.append(d[i][-1])
		return t


from collections import deque, defaultdict

class Solution:

	def bottomView(self, root):
		q = deque()
		q.append((root, -1))
		dic = defaultdict(list)
		while len(q) > 0:
			(node, ver) = q.popleft()
			if node.left:
				q.append((node.left, ver - 1))
			if node.right:
				q.append((node.right, ver + 1))
			dic[ver].append(node.data)
		res = []
		for ver in sorted(dic.keys()):
			res.append(dic[ver][-1])
		return res


class Solution:

	def bottomView(self, root):
		res = []
		d = {}
		q = deque()
		q.append([root, 0])
		while len(q):
			n = len(q)
			for i in range(n):
				p = q.popleft()
				d[p[1]] = p[0].data
				if p[0].left:
					q.append([p[0].left, p[1] - 1])
				if p[0].right:
					q.append([p[0].right, p[1] + 1])
		for i in sorted(d.keys()):
			res.append(d[i])
		return res


from collections import deque

class Solution:

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


class Solution:

	def bottomView(self, root):
		dict1 = {}
		dict2 = {}

		def dfs(root, d):
			nonlocal dict1
			if root != None:
				dict1[root] = d
				dfs(root.left, d - 1)
				dfs(root.right, d + 1)
		dfs(root, 0)
		mn = min(dict1.values())
		mx = max(dict1.values())
		l = 1
		list1 = [root]
		while l > 0:
			if dict1[list1[0]] in dict2:
				dict2[dict1[list1[0]]].append(list1[0].data)
			else:
				dict2[dict1[list1[0]]] = [list1[0].data]
			if list1[0].left:
				list1.append(list1[0].left)
				l += 1
			if list1[0].right:
				list1.append(list1[0].right)
				l += 1
			list1.pop(0)
			l -= 1
		list1 = []
		for i in range(mn, mx + 1):
			if i in dict2:
				list1.append(dict2[i][-1])
		return list1


class Solution:

	def bottomView(self, root):
		if not root:
			return
		q = [[root, 0]]
		res = []
		resHd = []
		nodes = {}
		maxHd = 0
		minHd = 0
		while q:
			curr = q.pop(0)
			currNode = curr[0]
			hd = curr[1]
			nodes[hd] = currNode.data
			if currNode.left:
				q.append([currNode.left, hd - 1])
				minHd -= 1
			if currNode.right:
				q.append([currNode.right, hd + 1])
				maxHd += 1
		for i in range(minHd, maxHd + 1):
			if i in nodes:
				res.append(nodes[i])
		return res


class Solution:

	def bottomView(self, root):
		if not root:
			return
		q = [[root, 0]]
		res = []
		resHd = []
		nodes = {}
		while q:
			curr = q.pop(0)
			currNode = curr[0]
			hd = curr[1]
			if hd in nodes:
				nodes[hd] = currNode.data
			else:
				nodes[hd] = currNode.data
			if currNode.left:
				q.append([currNode.left, hd - 1])
			if currNode.right:
				q.append([currNode.right, hd + 1])
		for i in nodes:
			resHd.append(i)
		resHd = sorted(resHd)
		for i in resHd:
			res.append(nodes[i])
		return res


class Solution:

	def bottomView(self, root):
		q = [[root, 0]]
		res = []
		m = {}
		while q:
			(curr, level) = q.pop(0)
			if level not in m:
				m[level] = curr.data
			elif level in m:
				m[level] = curr.data
			if curr.left:
				q.append((curr.left, level - 1))
			if curr.right:
				q.append((curr.right, level + 1))
		for i in sorted(m.keys()):
			res.append(m[i])
		return res


class Solution:

	def bottomView(self, a):
		ans = []
		if a == None:
			return ans
		stack = [(a, 0)]
		dic = {}
		while len(stack) != 0:
			(a, pos) = stack.pop(0)
			dic[pos] = a.data
			if a.left != None:
				stack.append((a.left, pos - 1))
			if a.right != None:
				stack.append((a.right, pos + 1))
		min1 = min(dic)
		max1 = max(dic)
		for i in range(min1, max1 + 1):
			ans.append(dic[i])
		return ans


class Solution:

	def bottomView(self, root):
		distance_val_map = {}

		def traverse(node, distance, level):
			nonlocal distance_val_map
			if not node:
				return
			if distance not in distance_val_map or distance_val_map[distance][1] <= level:
				distance_val_map[distance] = (node.data, level)
			traverse(node.left, distance - 1, level + 1)
			traverse(node.right, distance + 1, level + 1)
			return
		traverse(root, 0, 0)
		sorted_keys = list(distance_val_map.keys())
		sorted_keys.sort()
		res = []
		for key in sorted_keys:
			res.append(distance_val_map[key][0])
		return res


class Solution:

	def bottomView(self, root):
		d = {}
		q = deque()
		q.append((root, 0))
		while q:
			(node, dist) = q.popleft()
			d[dist] = node.data
			if node.left:
				q.append((node.left, dist - 1))
			if node.right:
				q.append((node.right, dist + 1))
		res = []
		for key in sorted(d.keys()):
			res.append(d[key])
		return res


class Solution:

	def bottomView(self, root):
		d = {}
		(x, y) = (0, 0)
		Q = [(root, 0)]
		while Q != []:
			(a, b) = Q.pop(0)
			if a.left:
				Q.append((a.left, b - 1))
			if a.right:
				Q.append((a.right, b + 1))
			x = min(b, x)
			y = max(b, y)
			d[b] = a.data
		ans = []
		for i in range(x, y + 1):
			ans.append(d[i])
		return ans


import collections

class Solution:

	def bottomView(self, root):
		q = []
		q.append((root, 0))
		hd = 0
		l = 0
		r = 0
		res = []
		dic = dict()
		while q:
			(curr, hd) = q.pop(0)
			if hd < l:
				l = hd
			if hd > r:
				r = hd
			dic[hd] = curr.data
			if curr.left:
				q.append((curr.left, hd - 1))
			if curr.right:
				q.append((curr.right, hd + 1))
		for i in range(l, r + 1):
			res.append(dic[i])
		return res