Given a Binary Tree, find Right view of it. Right view of a Binary Tree is set of nodes visible when tree is viewed from right side.
Right view of following tree is 1 3 7 8.
          1
       /     \
     2        3
   /   \      /    \
  4     5   6    7
    \
     8
Example 1:
Input:
       1
    /    \
   3      2
Output: 1 2
Example 2:
Input:
     10
    /   \
  20     30
 /   \
40  60 
Output: 10 30 60
Your Task:
Just complete the function rightView() that takes node as parameter and returns the right view as a list. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
0 ≤ Data of a node ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3







'''

# Node Class:

class Node:

    def init(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

class Solution:

    #Function to return list containing elements of right view of binary tree.

    def rightView(self,root):

        

        # code here

Solutions:
class Solution:

	def rightView(self, root):
		result = []
		q = []
		q.append(root)
		while q:
			leftmost = None
			length = len(q)
			for i in range(length):
				node = q.pop(0)
				if node:
					leftmost = node.data
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
					if i == length - 1:
						result.append(leftmost)
		return result


class Solution:

	def rightView(self, root):
		ret = []
		level = [root]
		while root and level:
			currentnodes = []
			nextlevel = []
			for node in level:
				currentnodes.append(node.data)
				if node.left:
					nextlevel.append(node.left)
				if node.right:
					nextlevel.append(node.right)
			ret.append(currentnodes[-1])
			level = nextlevel
		return ret


class Solution:

	def rightView(self, root):
		if root is None:
			a = []
			return a
		q = []
		q.append(root)
		ans = []
		while len(q) > 0:
			n = len(q)
			for i in range(n):
				temp = q.pop(0)
				if i == n - 1:
					ans.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
		return ans


class Solution:

	def rightView(self, root):
		ml = []

		def traversal(root, lv):
			if root == None:
				return
			if lv == len(ml):
				ml.append(root.data)
			traversal(root.right, lv + 1)
			traversal(root.left, lv + 1)
		traversal(root, 0)
		return ml


class Solution:

	def rightView(self, root):
		if not root:
			return []
		ans = []
		queue = deque([root])
		while queue:
			ans.append(queue[0].data)
			for i in range(len(queue)):
				tmp = queue.popleft()
				if tmp.right:
					queue.append(tmp.right)
				if tmp.left:
					queue.append(tmp.left)
		return ans


class Solution:

	def solve(self, root, d, lvl):
		if not root:
			return 0
		if lvl not in d:
			d[lvl] = root.data
		self.solve(root.right, d, lvl + 1)
		self.solve(root.left, d, lvl + 1)

	def rightView(self, root):
		d = {}
		ans = []
		self.solve(root, d, 1)
		for i in d:
			ans.append(d[i])
		return ans


class Solution:

	def rightViewTraversal(self, root, level, res):
		if root is None:
			return res
		if len(res) == level:
			res.append(root.data)
		self.rightViewTraversal(root.right, level + 1, res)
		self.rightViewTraversal(root.left, level + 1, res)

	def rightView(self, root):
		res = []
		if root is None:
			return res
		self.rightViewTraversal(root, 0, res)
		return res


class Solution:

	def rightView(self, root):
		rightMap = {}

		def traverse(root, level):
			if root == None:
				return
			if level not in rightMap:
				rightMap[level] = root.data
			traverse(root.right, level + 1)
			traverse(root.left, level + 1)
		traverse(root, 0)
		return rightMap.values()


class Solution:

	def rightView(self, root):
		q = []
		if root == None:
			return root
		q.append(root)
		a = []
		while len(q) != 0:
			s = len(q)
			temp = []
			while s > 0:
				t = q[0]
				temp.append(t.data)
				q.pop(0)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
				s = s - 1
			if len(temp) != 0:
				a.append(temp[len(temp) - 1])
		return a


class Solution:

	def rightView(self, root):

		def right(root, max_val, level):
			if root == None:
				return
			if level > max_val[0]:
				ans.append(root.data)
				max_val[0] = level
			right(root.right, max_val, level + 1)
			right(root.left, max_val, level + 1)
		ans = []
		right(root, [0], 1)
		return ans


from collections import deque

class Solution:

	def rightView(self, root):
		ans = []
		q = deque([root])
		if not root:
			return []
		while q:
			ans.append(q[-1].data)
			for _ in range(len(q)):
				x = q.popleft()
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
		return ans


class Solution:

	def rightView(self, root):
		if not root:
			return []
		result = []
		queue = [root]
		while queue:
			level_size = len(queue)
			for i in range(level_size):
				node = queue.pop(0)
				if i == level_size - 1:
					result.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return result


class Solution:

	def rightView(self, root):
		result = []
		queue = [root]
		level = []
		while queue != [] and root is not None:
			for node in queue:
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			result.append(node.data)
			queue = level
			level = []
		return result


class Solution:

	def rightView(self, root):
		s = []
		s.append(root)
		z = []
		while len(s) != 0:
			n = len(s)
			for i in range(n):
				node = s.pop(0)
				if i == n - 1:
					z.append(node.data)
				if node.left:
					s.append(node.left)
				if node.right:
					s.append(node.right)
		return z


class Solution:

	def rightView(self, root):
		if not root:
			return []
		res = []
		q = [root]
		while q:
			s = len(q)
			for i in range(s):
				back = q.pop(0)
				if i == 0:
					res.append(back.data)
				if back.right:
					q.append(back.right)
				if back.left:
					q.append(back.left)
		return res


class Solution:

	def rightView(self, root):

		def rightview(root, level, ans):
			if root is None:
				return
			if len(ans) < level:
				ans.append(root.data)
			rightview(root.right, level + 1, ans)
			rightview(root.left, level + 1, ans)
		ans = []
		rightview(root, 1, ans)
		return ans


class Solution:

	def rightView(self, root):
		myMap = {}

		def rightViewRecursive(node, level, hashMap):
			if node is None:
				return
			if level not in hashMap:
				hashMap[level] = node.data
			rightViewRecursive(node.right, level + 1, hashMap)
			rightViewRecursive(node.left, level + 1, hashMap)
		rightViewRecursive(root, 1, myMap)
		return myMap.values()


class Solution:

	def rightView(self, root):
		ans = []
		queue = [root]
		while queue:
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				if i == size - 1:
					ans.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return ans


from collections import deque

class Solution:

	def rightView(self, root):
		result = []
		queue = deque()
		queue.append(root)
		while len(queue) > 0:
			n = len(queue)
			while n > 0:
				n = n - 1
				element = queue.popleft()
				if n == 0:
					result.append(element.data)
				if element.left:
					queue.append(element.left)
				if element.right:
					queue.append(element.right)
		return result


class Solution:

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


from collections import deque

class Solution:

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


from collections import deque

class Solution:

	def rightView(self, root):
		dist_map = {}
		q = deque()
		q.append((root, 0))
		while q:
			(node, d) = q.popleft()
			dist_map[d] = node.data
			if node.left:
				q.append((node.left, d + 1))
			if node.right:
				q.append((node.right, d + 1))
		distances = sorted(dist_map.keys())
		ans = []
		for d in distances:
			ans.append(dist_map[d])
		return ans


class Solution:

	def rightView(self, root):
		res = []
		q = []
		if root == None:
			return []
		q.append(root)
		while q:
			l = len(q)
			for i in range(l):
				p = q.pop(0)
				if i == l - 1:
					res.append(p.data)
				if p.left != None:
					q.append(p.left)
				if p.right != None:
					q.append(p.right)
		return res


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		stack = [(root, 0)]
		result = []
		seen_lvl = set()
		while stack:
			(node, level) = stack.pop()
			if node is None:
				continue
			if level not in seen_lvl:
				result.append(node.data)
				seen_lvl.add(level)
			stack.append((node.left, level + 1))
			stack.append((node.right, level + 1))
		return result


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		ans = []
		queue = deque()
		queue.append(root)
		while queue:
			q_size = len(queue)
			ans.append(queue[0].data)
			for i in range(q_size):
				node = queue.popleft()
				if node.right:
					queue.append(node.right)
				if node.left:
					queue.append(node.left)
		return ans


class Solution:

	def rightView(self, root):
		res = []
		que = deque([root])
		while que:
			rightSide = None
			qLen = len(que)
			for i in range(qLen):
				node = que.popleft()
				if node:
					rightSide = node
					que.append(node.left)
					que.append(node.right)
			if rightSide:
				res.append(rightSide.data)
		return res


class Solution:

	def rightViewUtil(self, root, maxlevel, level, ans):
		if root:
			if level > maxlevel[0]:
				maxlevel[0] = level
				ans.append(root.data)
			self.rightViewUtil(root.right, maxlevel, level + 1, ans)
			self.rightViewUtil(root.left, maxlevel, level + 1, ans)

	def rightView(self, root):
		ans = []
		self.rightViewUtil(root, [-1], 0, ans)
		return ans


class Solution:

	def rec(self, node, level, arr):
		if node is None:
			return
		if len(arr) == level:
			arr.append(node.data)
		self.rec(node.right, level + 1, arr)
		self.rec(node.left, level + 1, arr)

	def rightView(self, root):
		arr = []
		self.rec(root, 0, arr)
		return arr


from collections import defaultdict

class Solution:

	def rightView(self, root):
		d = defaultdict(int)

		def h(root, lvl=0):
			if root == None:
				return
			d[lvl] = root.data
			h(root.left, lvl + 1)
			h(root.right, lvl + 1)
		ans = []
		h(root)
		for i in range(len(d)):
			ans.append(d[i])
		return ans


class Solution:

	def rightView(self, root):
		arr = []

		def rightview(root, arr, level):
			if root == None:
				return
			if level == len(arr):
				arr.append(root.data)
			rightview(root.right, arr, level + 1)
			rightview(root.left, arr, level + 1)
		rightview(root, arr, 0)
		return arr


class Solution:

	def rightView(self, root):
		if root == None:
			return []
		queue = []
		ans = []
		queue.append(root)
		while queue:
			n = len(queue)
			while n > 0:
				n -= 1
				temp = queue.pop(0)
				if n == 0:
					ans.append(temp.data)
				if temp.left != None:
					queue.append(temp.left)
				if temp.right != None:
					queue.append(temp.right)
		return ans


class Solution:

	def rightView(self, root):

		def rightViewUtil(root, curr_level, result):
			nonlocal max_level
			if not root:
				return
			if max_level < curr_level:
				max_level = curr_level
				result.append(root.data)
			rightViewUtil(root.right, curr_level + 1, result)
			rightViewUtil(root.left, curr_level + 1, result)
		result = []
		max_level = 0
		rightViewUtil(root, 1, result)
		return result


class Solution:

	def rightView(self, root):
		queue = []
		ans = []
		queue.append(root)
		while queue:
			level = []
			for i in range(len(queue)):
				curr = queue[0]
				queue.pop(0)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
				level.append(curr.data)
			ans.append(level)
		res = []
		for i in range(len(ans)):
			res.append(ans[i][-1])
		return res


class Solution:

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

		def solve(root, level):
			if not root:
				return
			if level == len(ans):
				ans.append(root.data)
			solve(root.right, level + 1)
			solve(root.left, level + 1)
		solve(root, 0)
		return ans


from collections import defaultdict

class Solution:

	def rightView(self, root):
		mp = defaultdict(int)

		def right_view(root, level):
			if root is None:
				return
			mp[level] = root.data
			right_view(root.left, level + 1)
			right_view(root.right, level + 1)
		right_view(root, 0)
		ans = []
		for key in sorted(mp.keys()):
			ans.append(mp[key])
		return ans


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		(level, sub) = ([], [])
		queue = [root, None]
		while len(queue) > 0:
			node = queue.pop(0)
			if node is None:
				if len(queue) == 0:
					break
				else:
					level.append(sub[-1])
					sub = []
					queue.append(None)
			else:
				sub.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		level.append(sub[-1])
		return level


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		q = deque()
		q.append(root)
		ans = []
		while q:
			n = len(q)
			i = 0
			while i < n:
				curr = q.popleft()
				i = i + 1
				if i == n:
					ans.append(curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
		return ans


class Solution:

	def rightView(self, root):
		(q, ans) = ([root], [])
		while len(q) > 0:
			ans.append(q[::-1][0].data)
			for i in range(len(q)):
				if q[0].left:
					q.append(q[0].left)
				if q[0].right:
					q.append(q[0].right)
				q.pop(0)
		return ans


class Solution:

	def rec_sol(self, root, ans, max_level, curr_level):
		if curr_level > max_level[0]:
			max_level[0] = curr_level
			ans.append(root.data)
		if root.right != None:
			self.rec_sol(root.right, ans, max_level, curr_level + 1)
		if root.left != None:
			self.rec_sol(root.left, ans, max_level, curr_level + 1)
		return

	def rightView(self, root):
		max_level = [-1]
		ans = []
		if root != None:
			self.rec_sol(root, ans, max_level, 0)
		return ans


class Solution:

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

	def rightView(self, root):
		dict = {}
		ans = []
		level = 0
		self.traversal(root, level, dict)
		for i in dict:
			ans.append(dict[i])
		return ans


class Solution:

	def rightView(self, root):
		a = []
		if root is None:
			return a

		def right(root, a, l):
			if root is None:
				return a
			if len(a) == l:
				a.append(root.data)
			right(root.right, a, l + 1)
			right(root.left, a, l + 1)
		right(root, a, 0)
		return a


class Solution:

	def rightView(self, root):
		l = [0]
		ans = []
		if root is None:
			return ans

		def fun(root, level):
			if root is None:
				return
			if l[0] < level:
				ans.append(root.data)
				l[0] = level
			fun(root.right, level + 1)
			fun(root.left, level + 1)
			return
		fun(root, 1)
		return ans


class Solution:

	def rightView(self, root):
		if not root:
			return
		q = [[root, 0]]
		(res, nodes) = ([], {})
		level = 0
		while q:
			(currNode, lvl) = q.pop(0)
			nodes[lvl] = currNode.data
			if currNode.left:
				q.append([currNode.left, lvl + 1])
				level += 1
			if currNode.right:
				q.append([currNode.right, lvl + 1])
				level += 1
		for i in range(0, level + 1):
			if i in nodes:
				res.append(nodes[i])
		return res


class Solution:

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


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		level_elements = [root]
		left_elements_values_list = []
		number_of_elements = 1
		while number_of_elements > 0:
			level_elements_list = []
			while number_of_elements:
				element = level_elements.pop(0)
				number_of_elements -= 1
				if element.left:
					level_elements.append(element.left)
				if element.right:
					level_elements.append(element.right)
				level_elements_list.append(element.data)
			left_elements_values_list.append(level_elements_list[-1])
			number_of_elements = len(level_elements)
		return left_elements_values_list


class Solution:

	def helperRightView(self, root, level, maxlevel, result):
		if root == None:
			return
		if maxlevel[0] < level:
			result.append(root.data)
			maxlevel[0] = level
		self.helperRightView(root.right, level + 1, maxlevel, result)
		self.helperRightView(root.left, level + 1, maxlevel, result)

	def rightView(self, root):
		maxlevel = [0]
		result = []
		self.helperRightView(root, 1, maxlevel, result)
		return result


class Solution:

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

		def traverse(root, max_level, level):
			if root is None:
				return
			if max_level[0] < level:
				ans.append(root.data)
				max_level[0] = level
			traverse(root.right, max_level, level + 1)
			traverse(root.left, max_level, level + 1)
		traverse(root, [0], 1)
		return ans


from queue import Queue

class Solution:

	def rightView(self, root):
		if root == None:
			return None
		q = Queue()
		result = list()
		q.put(root)
		while q.empty() == False:
			times = q.qsize()
			for i in range(times):
				root = q.get()
				if i == 0:
					result.append(root.data)
				if root.right != None:
					q.put(root.right)
				if root.left != None:
					q.put(root.left)
		return result


class Solution:

	def rightView(self, root):
		if not root:
			return []
		result = []
		q = deque([root])
		while q:
			size = len(q)
			for i in range(size):
				node = q.popleft()
				if i == size - 1:
					result.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return result


from collections import deque

class Solution:

	def rightView(self, root):
		if root is None:
			return []
		q = deque()
		q.append(root)
		count = 1
		ans = []
		while count:
			nums = count
			count = 0
			for i in range(nums):
				curr = q.popleft()
				if i == 0:
					ans.append(curr.data)
				if curr.right:
					q.append(curr.right)
					count += 1
				if curr.left:
					q.append(curr.left)
					count += 1
		return ans


class Solution:

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

	def rightView(self, root):
		dic = {}
		self.getT(root, 1, dic)
		arr = []
		for (ar, val) in dic.items():
			arr.append(val[0])
		return arr


class Solution:

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

		def h(root, ver=0, lvl=0):
			if root == None:
				return
			if len(ans) == lvl:
				ans.append(root.data)
			ans[lvl] = root.data
			h(root.left, ver - 1, lvl + 1)
			h(root.right, ver + 1, lvl + 1)
		h(root)
		return ans


class Solution:

	def rightView(self, root):
		di = {}

		def h(root, ver=0, lvl=0):
			if root == None:
				return
			di[lvl] = root.data
			h(root.left, ver - 1, lvl + 1)
			h(root.right, ver + 1, lvl + 1)
		h(root)
		ans = []
		for i in range(len(di)):
			ans.append(di[i])
		return ans


def traverse(root, h, hash_map):
	if root == None:
		return
	else:
		if h not in hash_map:
			hash_map[h] = root.data
		traverse(root.right, h + 1, hash_map)
		traverse(root.left, h + 1, hash_map)
		return

class Solution:

	def rightView(self, root):
		h = 0
		hash_map = {}
		traverse(root, h, hash_map)
		k = 0
		ans = []
		while k in hash_map:
			ans.append(hash_map[k])
			k += 1
		return ans


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		q = []
		L = []
		q.append(root)
		while q:
			size = len(q)
			for i in range(0, size):
				curr = q.pop(0)
				if i == size - 1:
					L.append(curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
		return L


class Solution:

	def rightView(self, root):
		if root == None:
			return []
		q = deque()
		q.append(root)
		k = []
		while q:
			v = len(q)
			k.append(q[-1].data)
			for i in range(0, v):
				temp = q.popleft()
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
		return k


class Solution:

	def rightView(self, root):
		if root is None:
			return 0
		arr = []
		q = deque()
		q.append(root)
		while q:
			count = len(q)
			arr.append(q[-1].data)
			for i in range(count):
				node = q.popleft()
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
		return arr


class Solution:

	def rightView(self, root):

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


class Solution:

	def rightViewUtil(self, root, level, max_level, l):
		if root is None:
			return
		if max_level[0] < level:
			(l.append(root.data),)
			max_level[0] = level
		self.rightViewUtil(root.right, level + 1, max_level, l)
		self.rightViewUtil(root.left, level + 1, max_level, l)

	def rightView(self, root):
		max_level = [0]
		l = []
		self.rightViewUtil(root, 1, max_level, l)
		return l


class Solution:

	def rightView(self, root):
		arr = []

		def left(node, depth):
			if not node:
				return
			if depth == len(arr):
				arr.append(node.data)
			left(node.right, depth + 1)
			left(node.left, depth + 1)
		left(root, 0)
		return arr


class Solution:

	def rightView(self, head):
		q = [head]
		q1 = []
		o = []
		i = 0
		while head != None:
			if head.left != None:
				q1.append(head.left)
			if head.right != None:
				q1.append(head.right)
			if head == q[-1]:
				if q1 == []:
					o.append(head.data)
					break
				q = []
				q += q1
				q1 = []
				o.append(head.data)
				head = q[0]
			elif head != q[-1]:
				q.pop(0)
				head = q[0]
		return o


class Solution:

	def getView(self, root, li):
		q = [root]
		while q:
			level_nodes = []
			size = len(q)
			for _ in range(size):
				node = q.pop(0)
				level_nodes.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			li.append(level_nodes[-1])
		return li

	def rightView(self, root):
		li = []
		self.getView(root, li)
		return li


class Solution:

	def rightView(self, root):
		ans = []
		res = []
		que = [root]
		while que:
			l = len(que)
			ans = []
			for i in range(0, l):
				node = que.pop(0)
				if node.left:
					que.append(node.left)
				if node.right:
					que.append(node.right)
				ans.append(node.data)
			res.append(ans[-1])
		return res


class Solution:

	def rightView(self, root):
		q = [[root, 0]]
		d = {}
		while q:
			t = q.pop(0)
			temp = t[0]
			level = t[1]
			if temp:
				d[level] = temp.data
			if temp.left:
				q.append([temp.left, level + 1])
			if temp.right:
				q.append([temp.right, level + 1])
		l = []
		for (k, v) in d.items():
			l.append(v)
		return l


class Solution:

	def rightView(self, root):
		from collections import deque
		q = deque()
		q.append(root)
		result = list()
		while q:
			cur_len_q = len(q)
			i = 0
			while i < cur_len_q:
				cur = q.popleft()
				if cur is None:
					i += 1
					continue
				if i + 1 == cur_len_q:
					result.append(cur.data)
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
				i += 1
		return result


class Solution:

	def rightView(self, root):
		ans = []
		queue = []
		queue.append(root)
		ans.append(root.data)
		while queue:
			another = []
			while queue:
				node = queue.pop(0)
				if node.left:
					another.append(node.left)
				if node.right:
					another.append(node.right)
			if another != []:
				ans.append(another[-1].data)
			queue = another
		return ans


class Solution:

	def rightView(self, root):
		stack = [root]
		ans = []
		if root is None:
			return ans
		while len(stack) > 0:
			n = len(stack)
			for i in range(1, n + 1):
				if i == 1:
					x = stack.pop(0)
					ans.append(x.data)
					if x.right:
						stack.append(x.right)
					if x.left:
						stack.append(x.left)
				else:
					x = stack.pop(0)
					if x.right:
						stack.append(x.right)
					if x.left:
						stack.append(x.left)
		return ans


class Solution:

	def rightView(self, root):
		if root is None:
			return []
		res = []
		max = [0]

		def view(node, level):
			if node is None:
				return []
			if level > max[0]:
				res.append(node.data)
				max[0] = level
			view(node.right, level + 1)
			view(node.left, level + 1)
			return res
		view(root, 1)
		return res


class Solution:

	def rightView(self, root):

		def rec(root, level, res):
			if not root:
				return res
			if level > len(res):
				res.append(root.data)
			rec(root.right, level + 1, res)
			rec(root.left, level + 1, res)
			return res
		return rec(root, 1, [])
		if not root:
			return []
		q = [root]
		res = []
		while q:
			n = len(q)
			for i in range(n):
				node = q.pop(0)
				if i == n - 1:
					res.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return res


def reversepreorder(root, level, s):
	if root == None:
		return
	if level == len(s):
		s.append(root.data)
	reversepreorder(root.right, level + 1, s)
	reversepreorder(root.left, level + 1, s)

class Solution:

	def rightView(self, root):
		if root == None:
			return root
		s = []
		level = 0
		reversepreorder(root, level, s)
		return s


def solve(root, q, level):
	if root == None:
		return q
	if len(q) == level:
		q.append(root.data)
	solve(root.right, q, level + 1)
	solve(root.left, q, level + 1)

class Solution:

	def rightView(self, root):
		q = []
		solve(root, q, 0)
		return q


class Solution:

	def rightView(self, root):
		queue = []
		queue.append(root)
		s = []
		while len(queue) != 0:
			size = len(queue)
			while size > 0:
				size -= 1
				temp = queue.pop(0)
				if size == 0:
					s.append(temp.data)
				if temp.left != None:
					queue.append(temp.left)
				if temp.right != None:
					queue.append(temp.right)
		return s


from collections import deque

class Solution:

	def rightView(self, root):
		(q, res) = (deque(), [])
		q.append(root)
		while q:
			res.append(q[-1].data)
			nq = deque()
			while q:
				top = q.popleft()
				if top.left:
					nq.append(top.left)
				if top.right:
					nq.append(top.right)
			q = nq
		return res


class Solution:

	def rightView(self, root):
		if root is None:
			return
		queue = []
		queue.append(root)
		res = []
		while queue:
			n = len(queue)
			while n > 0:
				n -= 1
				node = queue.pop(0)
				if n == 0:
					res.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return res


from collections import deque

class Solution:

	def rightView(self, root):
		if root is None:
			return
		queue = deque()
		queue.append(root)
		res = []
		while queue:
			n = len(queue)
			while n > 0:
				n -= 1
				node = queue.popleft()
				if n == 0:
					res.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return res