Given a binary tree of size N, find its reverse level order traversal. ie- the traversal must begin from the last level. 
Example 1:
Input :
        1
      /   \
     3     2
Output: 3 2 1
Explanation:
Traversing level 1 : 3 2
Traversing level 0 : 1
Example 2:
Input :
       10
      /  \
     20   30
    / \ 
   40  60
Output: 40 60 20 30 10
Explanation:
Traversing level 2 : 40 60
Traversing level 1 : 20 30
Traversing level 0 : 10
Your Task:  
You dont need to read input or print anything. Complete the function reverseLevelOrder() which takes the root of the tree as input parameter and returns a list containing the reverse level order traversal of the given tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^4

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

def reverseLevelOrder(root):

    # code here

Solutions:
def reverseLevelOrder(root):
	temp1 = [root]
	result = []
	while temp1:
		temp2 = []
		temp3 = []
		for i in temp1:
			temp3.append(i.data)
			if i.left:
				temp2.append(i.left)
			if i.right:
				temp2.append(i.right)
		temp1 = temp2
		if temp3:
			result = temp3 + result
	return result


def reverseLevelOrder(root):
	if root is None:
		return
	queue = [root]
	res = []
	while queue:
		pointer = queue.pop(0)
		res.append(pointer.data)
		if pointer.right is not None:
			queue.append(pointer.right)
		if pointer.left is not None:
			queue.append(pointer.left)
	res.reverse()
	return res


def reverseLevelOrder(root):
	if root == None:
		return []
	res = []
	dequeue = []
	dequeue.append(root)
	while len(dequeue) > 0:
		node = dequeue.pop(0)
		if node.right != None:
			dequeue.append(node.right)
		if node.left != None:
			dequeue.append(node.left)
		res.insert(0, node.data)
	return res


def reverseLevelOrder(root):
	q = [root]
	res = []
	while q:
		l = len(q)
		t = []
		for i in range(l):
			p = q.pop(0)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
			t.append(p.data)
		res = t + res
	return res


def reverseLevelOrder(root):
	a = []
	if root == None:
		return root
	a.append(root)
	q = []
	q.append(root.data)
	while len(a) != 0:
		t = a[0]
		if t.right:
			q.append(t.right.data)
			a.append(t.right)
		if t.left:
			q.append(t.left.data)
			a.append(t.left)
		a.pop(0)
	q1 = []
	for i in range(len(q) - 1, -1, -1):
		q1.append(q[i])
	return q1


from collections import deque

def reverseLevelOrder(root):
	q = deque([root])
	ans = deque([])
	while q:
		x = q.popleft()
		if x.right:
			q.append(x.right)
		if x.left:
			q.append(x.left)
		ans.appendleft(x.data)
	return ans


def reverseLevelOrder(root):
	if root == None:
		return []
	q = [root]
	ans = []
	while q:
		nod = q.pop(0)
		ans.append(nod.data)
		if nod.right:
			q.append(nod.right)
		if nod.left:
			q.append(nod.left)
	return ans[::-1]


def reverseLevelOrder(root):
	q = []
	z = []
	q.append(root)
	while len(q) != 0:
		res = []
		n = len(q)
		for i in range(n):
			node = q.pop(0)
			res.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		res.reverse()
		for i in range(len(res)):
			z.append(res[i])
	z.reverse()
	return z


def reverseLevelOrder(root):
	q = []
	q.append(root)
	ans = []
	while q:
		node = q.pop(0)
		if node:
			ans.insert(0, node.data)
			if node.right:
				q.append(node.right)
			if node.left:
				q.append(node.left)
	return ans


def reverseLevelOrder(root):
	res = []
	q = deque()
	q.append(root)
	while q:
		node = q.popleft()
		if node:
			res.append(node.data)
			q.append(node.right)
			q.append(node.left)
	return res[::-1]


def reverseLevelOrder(root):
	ans = []
	stack = []
	queue = deque()
	queue.append(root)
	while len(queue) != 0:
		front = queue[0]
		stack.append(front)
		if front.right:
			queue.append(front.right)
		if front.left:
			queue.append(front.left)
		queue.popleft()
	while len(stack) != 0:
		ans.append(stack[-1].data)
		stack.pop()
	return ans


from collections import deque

def reverseLevelOrder(root):
	q = deque()
	ans = deque()
	q.append(root)
	while len(q) != 0:
		node = q.popleft()
		ans.appendleft(node.data)
		if node.right is not None:
			q.append(node.right)
		if node.left is not None:
			q.append(node.left)
	return ans


def reverseLevelOrder(root):
	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 = [node.data for node in temp] + ans
	return ans


def reverseLevelOrder(root):
	q = [root]
	l = []
	while len(q) > 0:
		k = q.pop(0)
		l.append(k.data)
		if k.right != None:
			q.append(k.right)
		if k.left != None:
			q.append(k.left)
	return l[::-1]


def reverseLevelOrder(root):
	st = []
	q = []
	q.append(root)
	while len(q) != 0:
		curr = q.pop(0)
		st.append(curr.data)
		if curr.right != None:
			q.append(curr.right)
		if curr.left != None:
			q.append(curr.left)
	return st[::-1]


class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None
m = 0
dicti = {}

def recur(root, val):
	global dicti
	global m
	if root == None:
		return
	elif val + 1 in dicti.keys():
		if val + 1 > m:
			m = val + 1
		dicti[val + 1].append(root.data)
	elif val + 1 not in dicti.keys():
		if val + 1 > m:
			m = val + 1
		dicti[val + 1] = []
		dicti[val + 1].append(root.data)
	recur(root.left, val + 1)
	recur(root.right, val + 1)

def reverseLevelOrder(root):
	global dicti
	global m
	dicti = {}
	m = 0
	u = []
	recur(root, 0)
	p = max(dicti.keys())
	for i in range(p, 0, -1):
		for j in dicti[i]:
			u.append(j)
	return u


def reverseLevelOrder(root):
	queue = []
	ans = []
	queue.append(root)
	while len(queue) != 0:
		ele = queue.pop(0)
		ans.append(ele.data)
		if ele.right != None:
			queue.append(ele.right)
		if ele.left != None:
			queue.append(ele.left)
	return ans[::-1]


def reverseLevelOrder(root):
	q = deque()
	ans = []
	q.append(root)
	while q:
		root = q.popleft()
		ans.append(root.data)
		if root.right:
			q.append(root.right)
		if root.left:
			q.append(root.left)
	i = 0
	j = len(ans) - 1
	while i < j:
		(ans[i], ans[j]) = (ans[j], ans[i])
		i += 1
		j -= 1
	return ans


def reverseLevelOrder(root):

	def _reverseLevelOrder(root, level, res):
		if not root:
			return
		if level < len(res):
			res[level].append(root.data)
		else:
			res.append([root.data])
		_reverseLevelOrder(root.left, level + 1, res)
		_reverseLevelOrder(root.right, level + 1, res)
	res = []
	_reverseLevelOrder(root, 0, res)
	return [j for i in res[::-1] for j in i]


def reverseLevelOrder(root):
	q = deque()
	q.append(root)
	q.append('$')
	answer = []
	temp = []
	while q:
		e = q.popleft()
		if e == '$':
			answer = [*temp, *answer]
			if not q:
				break
			else:
				temp = []
				q.append('$')
		else:
			temp.append(e.data)
			if e.left:
				q.append(e.left)
			if e.right:
				q.append(e.right)
	return answer


def reverseLevelOrder(root):
	q = [root]
	l = []
	while q:
		t = q.pop(0)
		l.append(t.data)
		if t.right:
			q.append(t.right)
		if t.left:
			q.append(t.left)
	return l[::-1]


def reverseLevelOrder(root):
	res = []
	temp = [root]
	while temp:
		tmp = []
		tmp1 = []
		for i in temp:
			tmp1.append(i.data)
			if i.left:
				tmp.append(i.left)
			if i.right:
				tmp.append(i.right)
		temp = tmp
		if tmp1:
			res = tmp1 + res
	return res


def reverseLevelOrder(root):
	q = []
	result = []
	ans = []
	q.append(root)
	while q:
		node = q.pop(0)
		result.append(node)
		if node.right:
			q.append(node.right)
		if node.left:
			q.append(node.left)
	while len(result) > 0:
		a = result.pop()
		ans.append(a.data)
	return ans


def reverseLevelOrder(root):
	s = []
	q = []
	q.append(root)
	while len(q) != 0:
		node = q.pop(0)
		s.append(node.data)
		if node.right:
			q.append(node.right)
		if node.left:
			q.append(node.left)
	return s[::-1]


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


def reverseLevelOrder(root):
	s1 = [root]
	s2 = []
	ans = [root]
	while len(s1) > 0:
		for i in s1:
			if i.right:
				s2.append(i.right)
			if i.left:
				s2.append(i.left)
		s1 = s2
		ans = ans + s2
		s2 = []
	for i in range(len(ans)):
		ans[i] = ans[i].data
	return ans[::-1]


def reverseLevelOrder(root):
	order = []
	queue = []
	queue.append(root)
	while len(queue) > 0:
		temp = queue.pop(0)
		order.append(temp.data)
		if temp.right and temp.right.data:
			queue.append(temp.right)
		if temp.left and temp.left.data:
			queue.append(temp.left)
	i = 0
	j = len(order) - 1
	while i < j:
		temp = order[i]
		order[i] = order[j]
		order[j] = temp
		i = i + 1
		j = j - 1
	return order


from collections import deque

def reverseLevelOrder(root):
	q = deque()
	ans = []
	q.append(root)
	while q:
		tp = q.popleft()
		ans.append(tp.data)
		if tp.right:
			q.append(tp.right)
		if tp.left:
			q.append(tp.left)
	return ans[::-1]


from collections import deque

def reverseLevelOrder(root):
	resultlist = list()
	dQ = deque()
	if root != None:
		dQ.append(root)
		resultlist.append(root.data)
	while dQ:
		times = len(dQ)
		for i in range(times):
			holdnode = dQ.popleft()
			if holdnode.left != None:
				dQ.append(holdnode.left)
			if holdnode.right != None:
				dQ.append(holdnode.right)
		for dataset in reversed(dQ):
			resultlist.append(dataset.data)
	resultlist.reverse()
	return resultlist


def reverseLevelOrder(root):
	if root is None:
		return
	queue = []
	l1 = []
	queue.append(root)
	while len(queue) > 0:
		l1.append(queue[0].data)
		node = queue.pop(0)
		if node.right:
			queue.append(node.right)
		if node.left:
			queue.append(node.left)
	return l1[::-1]


def reverseLevelOrder(root):
	if root is None:
		return
	q = []
	x = []
	q.append(root)
	while len(q) > 0:
		x.append(q[0].data)
		root = q.pop(0)
		if root.right is not None:
			q.append(root.right)
		if root.left is not None:
			q.append(root.left)
	return x[::-1]


def reverseLevelOrder(root):
	q = deque()
	q.append(root)
	ans = deque()
	while q:
		node = q.popleft()
		if node is None:
			continue
		ans.appendleft(node.data)
		if node.right:
			q.append(node.right)
		if node.left:
			q.append(node.left)
	return ans


from collections import deque

def reverseLevelOrder(root):
	if not root:
		return []
	q = deque([root])
	stack = []
	while q:
		node = q.popleft()
		stack.append(node)
		if node.right:
			q.append(node.right)
		if node.left:
			q.append(node.left)
	ans = []
	while stack:
		node = stack.pop()
		ans.append(node.data)
	return ans


def reverseLevelOrder(root):
	q = []
	v = []
	a = []
	q.append(root)
	while len(q) != 0:
		temp = q.pop(0)
		if temp.right != None:
			q.append(temp.right)
		if temp.left != None:
			q.append(temp.left)
		v.append(temp)
	while len(v) != 0:
		a.append(v.pop().data)
	return a


from collections import deque

def reverseLevelOrder(root):
	if root is None:
		return []
	if root.left is None and root.right is None:
		return [root.data]
	q = deque()
	count = 1
	q.append(root)
	ans = []
	while count:
		curr = q.popleft()
		count -= 1
		ans.append(curr.data)
		if curr.right:
			q.append(curr.right)
			count += 1
		if curr.left:
			q.append(curr.left)
			count += 1
	ans.reverse()
	return ans


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

def reverseLevelOrder(root):
	if root == None:
		return root
	h = 0
	hash_map = {}
	traverse(root, h, hash_map)
	max_h = max(list(hash_map.keys()))
	ans = []
	while max_h in hash_map:
		ans.extend(hash_map[max_h])
		max_h -= 1
	return ans


def reverseLevelOrder(root):
	(queue, ans) = ([root], [])
	while len(queue) > 0:
		nn = queue.pop(0)
		if nn.right:
			queue.append(nn.right)
		if nn.left:
			queue.append(nn.left)
		ans.append(nn.data)
	return ans[::-1]


def reverseLevelOrder(root):
	queue = []
	stack = []
	queue.append(root)
	while len(queue) > 0:
		node = queue.pop(0)
		stack.append(node.data)
		if node.right:
			queue.append(node.right)
		if node.left:
			queue.append(node.left)
	return stack[::-1]


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


def reverseLevelOrder(root):
	ans = []
	queue = []
	queue.append(root)
	while queue:
		node = queue.pop(0)
		ans.insert(0, node.data)
		if node.right is not None:
			queue.append(node.right)
		if node.left is not None:
			queue.append(node.left)
	return ans


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

def reverseLevelOrder(root):
	ans = []
	fun(root, 0, ans)
	l = []
	ans = ans[::-1]
	for i in ans:
		l.extend(i)
	return l


def reverseLevelOrder(root):
	if root == None:
		return root
	q = []
	arr = []
	q.append(root)
	while len(q) != 0:
		root = q.pop(0)
		arr.append(root.data)
		if root.right is not None:
			q.append(root.right)
		if root.left is not None:
			q.append(root.left)
	return reversed(arr)


def reverseLevelOrder(root):

	def traversal(root, q, st):
		while q:
			node = q.pop(0)
			if node is not None:
				st.append(node.data)
				q.append(node.right)
				q.append(node.left)
		return st
	ans = []
	st = []
	q = [root]
	traversal(root, q, st)
	while st:
		ans.append(st.pop())
	return ans


def reverseLevelOrder(root):
	if root == None:
		return []
	temp = [root]
	res = []
	while temp:
		(r1, r2) = ([], [])
		for i in temp:
			r1.append(i.data)
			if i.left:
				r2.append(i.left)
			if i.right:
				r2.append(i.right)
		temp = r2
		res = r1 + res
	return res


def reverseLevelOrder(root):
	from collections import deque
	q = deque()
	q.append(root)
	stack = []
	result = list()
	while q:
		sublist = deque()
		cur_len_q = len(q)
		for _ in range(cur_len_q):
			cur = q.popleft()
			sublist.append(cur.data)
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
		stack.append(sublist)
	while stack:
		sublist = stack.pop()
		while sublist:
			result.append(sublist.popleft())
	return result


def ro(root, arr):
	qu = [root]
	i = 0
	while i < len(qu):
		if qu[i].right:
			qu.append(qu[i].right)
		if qu[i].left:
			qu.append(qu[i].left)
		i += 1
	for i in qu[::-1]:
		print(i.data, end=' ')

def reverseLevelOrder(root):
	arr = []
	ro(root, arr)
	return arr


def reverseLevelOrder(root):
	if root is None:
		return root
	stack = [root]
	ans = []
	while len(stack) > 0:
		x = stack.pop(0)
		if x.right:
			stack.append(x.right)
		if x.left:
			stack.append(x.left)
		ans.append(x.data)
	return ans[::-1]


def reverseLevelOrder(root):
	q = [[root, 0]]
	res = []
	temp1 = []
	temp2 = []
	while q:
		t = q.pop(0)
		temp = t[0]
		level = t[1]
		if level % 2 == 0:
			if temp2:
				res.append(temp2)
			temp2 = []
			temp1.append(temp.data)
		else:
			if temp1:
				res.append(temp1)
			temp1 = []
			temp2.append(temp.data)
		if temp.left:
			q.append([temp.left, level + 1])
		if temp.right:
			q.append([temp.right, level + 1])
	if temp1:
		res.append(temp1)
	if temp2:
		res.append(temp2)
	f = []
	for row in res[::-1]:
		for i in row:
			f.append(i)
	return f


def reverseLevelOrder(root):
	queue = []
	res = []
	queue.append(root)
	while queue:
		curr = queue.pop(0)
		res.append(curr.data)
		if curr.right:
			queue.append(curr.right)
		if curr.left:
			queue.append(curr.left)
	return reversed(res)


def reverseLevelOrder(root):
	(de, ans, check) = (deque([None, root]), [], [])
	while de:
		x = de.pop()
		if not x:
			if de:
				de.appendleft(None)
			ans += reversed(check)
			check = []
		else:
			check.append(x.data)
			if x.left:
				de.appendleft(x.left)
			if x.right:
				de.appendleft(x.right)
	ans.reverse()
	return ans


def reverseLevelOrder(root):
	if not root:
		return root
	q = [root]
	res = []
	while q:
		node = q.pop(0)
		res.append(node.data)
		if node.right:
			q.append(node.right)
		if node.left:
			q.append(node.left)
	return res[::-1]


def reverseLevelOrder(root):
	q = [root]
	ans = []
	while q:
		n = len(q)
		result = []
		for i in range(n):
			curr = q.pop(0)
			result.append(curr.data)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
		ans.append(result)
	final = []
	for i in reversed(ans):
		final += i
	return final


def reverseLevelOrder(root):
	res = []
	if root == None:
		return None
	q = []
	q.append(root)
	while len(q) != 0:
		res.append(q[0].data)
		node = q.pop(0)
		if node.right != None:
			q.append(node.right)
		if node.left != None:
			q.append(node.left)
	return reversed(res)


def reverseLevelOrder(root):
	q = [root]
	res = []
	while q:
		s = q.pop(0)
		res.append(s.data)
		if s.right:
			q.append(s.right)
		if s.left:
			q.append(s.left)
	res.reverse()
	return res


def reverseLevelOrder(root):
	q = [root]
	ans = []
	while len(q) > 0:
		temp = q.pop(0)
		ans.append(temp.data)
		if temp.right:
			q.append(temp.right)
		if temp.left:
			q.append(temp.left)
	return ans[::-1]


def reverseLevelOrder(root):
	queue = [root]
	listt = []
	ini = 0
	count = 1
	ini2 = 0
	count2 = 0
	new_queue = []
	listt2 = []
	while ini < count:
		a = queue[ini]
		ini += 1
		listt2.append(a.data)
		if a.left != None:
			new_queue.append(a.left)
			count2 += 1
		if a.right != None:
			new_queue.append(a.right)
			count2 += 1
		if ini == count:
			listt = listt2 + listt
			queue = new_queue
			new_queue = []
			count = count2
			count2 = 0
			listt2 = []
			ini = 0
	return listt


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


def reverseLevelOrder(root):
	q = []
	q.append(root)
	ans = []
	while len(q) > 0:
		frontNode = q.pop(0)
		ans.append(frontNode.data)
		if frontNode.right:
			q.append(frontNode.right)
		if frontNode.left:
			q.append(frontNode.left)
	ans.reverse()
	return ans


def reverseLevelOrder(root):
	q = []
	q.append(root)
	res = []
	while len(q) > 0:
		size = len(q)
		ans = [0] * size
		for i in range(size):
			frontNode = q.pop(0)
			ans[i] = frontNode.data
			if frontNode.left:
				q.append(frontNode.left)
			if frontNode.right:
				q.append(frontNode.right)
		res.append(ans)
	result = []
	for i in range(len(res) - 1, -1, -1):
		for j in range(len(res[i])):
			result.append(res[i][j])
	return result


from collections import deque

def reverseLevelOrder(root):
	if root == None:
		return None
	q = deque()
	q.append(root)
	ans = []
	while q:
		lis = []
		for i in range(len(q)):
			node = q.popleft()
			if node:
				q.append(node.left)
				q.append(node.right)
				lis.append(node.data)
		if lis:
			ans += lis[::-1]
	return ans[::-1]


def reverseLevelOrder(root):
	d = []
	_levelOrder([root], d)
	return d

def _levelOrder(queue, answer):
	new_ls = []
	for i in queue:
		if i:
			new_ls.append(i.left)
			new_ls.append(i.right)
	if new_ls:
		_levelOrder(new_ls, answer)
		for i in queue:
			if i:
				answer.append(i.data)


def check(root, lst):
	if root:
		check(root.left, lst)
		check(root.right, lst)
		lst.append(root.data)

def reverseLevelOrder(root):
	lst = []
	q = deque()
	q.append(root)
	while q:
		n = q.popleft()
		if n is Node:
			continue
		lst.append(n.data)
		if n.right:
			q.append(n.right)
		if n.left:
			q.append(n.left)
	lst.reverse()
	return lst


def reverseLevelOrder(root):
	from collections import deque
	q = deque()
	if root:
		q.append(root)
	ans = []
	while q:
		size = len(q)
		l = []
		for i in range(size):
			node = q.popleft()
			l += [node.data]
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		ans = l + ans
	return ans


def reverseLevelOrder(root):
	result = []
	queue = [root]
	while len(queue) != 0:
		lst = []
		for i in range(len(queue)):
			curr = queue.pop(0)
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
			lst.append(curr.data)
		result.append(lst)
	new_result = []
	for i in range(len(result) - 1, -1, -1):
		new_result.extend(result[i])
	return new_result


def reverseLevelOrder(root):
	q = []
	ans = []
	q.append(root)
	while len(q) != 0:
		curr = q.pop(0)
		ans.append(curr.data)
		if curr.right != None:
			q.append(curr.right)
		if curr.left != None:
			q.append(curr.left)
	ans.reverse()
	return ans


from collections import deque as dq

def reverseLevelOrder(root):
	if root is None:
		return
	ans = []
	q = dq()
	q.append(root)
	while len(q) > 0:
		curr = q.popleft()
		ans.append(curr.data)
		leftChild = curr.left
		rightChild = curr.right
		if rightChild:
			q.append(rightChild)
		if leftChild:
			q.append(leftChild)
	return ans[::-1]


def reverseLevelOrder(root):
	all_levels = []
	queue = []
	queue.append(root)
	while queue:
		queue_len = len(queue)
		level_elements = []
		while queue_len > 0:
			node = queue.pop(0)
			level_elements.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			queue_len -= 1
		all_levels.append(level_elements)
	reverse = []
	for level in range(len(all_levels) - 1, -1, -1):
		reverse.extend(all_levels[level])
	return reverse


def reverseLevelOrder(root):
	ans = []
	queue = [root]
	while len(queue):
		n = len(queue)
		temp = []
		while n > 0:
			node = queue.pop(0)
			temp.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			n = n - 1
		ans.append(temp)
	an = []
	ans = ans[::-1]
	for i in ans:
		for j in i:
			an.append(j)
	return an


import collections

def reverseLevelOrder(root):
	res = collections.deque()

	def bfs(node):
		q = collections.deque()
		q.append(node)
		while q:
			ele = q.popleft()
			res.appendleft(ele.data)
			if ele.right:
				q.append(ele.right)
			if ele.left:
				q.append(ele.left)
		return res
	ans = bfs(root)
	return ans


def reverseLevelOrder(root):
	if root == None:
		return -1
	(x, l) = ([], [])
	x.append(root)
	l.append(root.data)
	while x:
		a = len(x)
		y = []
		for i in range(0, a):
			if x[0].left:
				x.append(x[0].left)
				y.append(x[0].left.data)
			if x[0].right:
				x.append(x[0].right)
				y.append(x[0].right.data)
			x.pop(0)
		l.extend(y[-1::-1])
	return l[-1::-1]


def reverseLevelOrder(root):
	from queue import Queue
	if root is None:
		return []
	q = Queue()
	q.put(root)
	ans = []
	while q.qsize() != 0:
		cur = q.get()
		ans.append(cur.data)
		if cur.right is not None:
			q.put(cur.right)
		if cur.left is not None:
			q.put(cur.left)
	return ans[::-1]


def reverseLevelOrder(root):
	q = []
	ans = []
	q.append(root)
	while len(q) != 0:
		t = q.pop(0)
		ans.append(t.data)
		if t.right:
			q.append(t.right)
		if t.left:
			q.append(t.left)
		elif len(q) == 0:
			break
	return reversed(ans)


def reverseLevelOrder(root):
	ans = deque()
	if root == None:
		return result
	q = deque()
	q.append(root)
	while len(q) != 0:
		size = len(q)
		stack = []
		for i in range(size):
			element = q.popleft()
			stack.append(element.data)
			if element.left:
				q.append(element.left)
			if element.right:
				q.append(element.right)
		while len(stack) != 0:
			val = stack.pop()
			ans.appendleft(val)
	return ans


def reverseLevelOrder(root):
	if not root:
		return
	q = deque()
	q.append(root)
	res = []
	ans = []
	while len(q):
		lev = []
		for i in range(len(q)):
			el = q.popleft()
			lev.append(el.data)
			if el.left:
				q.append(el.left)
			if el.right:
				q.append(el.right)
		res.append(lev)
	for i in range(len(res) - 1, -1, -1):
		for j in res[i]:
			ans.append(j)
	return ans


def reverseLevelOrder(root):
	l = []
	q = []
	q.append(root)
	while q:
		z = q.pop(0)
		l.insert(0, z.data)
		if z.right is not None:
			q.append(z.right)
		if z.left is not None:
			q.append(z.left)
	return l


def reverseLevelOrder(root):
	if root == None:
		return None
	queue = []
	res = []
	queue.append(root)
	while queue:
		res.append(queue[0].data)
		currentNode = queue.pop(0)
		if currentNode.right:
			queue.append(currentNode.right)
		if currentNode.left:
			queue.append(currentNode.left)
	res.reverse()
	return res


def reverseLevelOrder(root):
	q = []
	ans = []
	q.append(root)
	while q != []:
		root = q.pop(0)
		ans.append(root.data)
		if root.right is not None:
			q.append(root.right)
		if root.left is not None:
			q.append(root.left)
	ans.reverse()
	return ans


def reverseLevelOrder(root):
	if root is None:
		return None
	answer = deque()
	q = deque()
	q.append(root)
	while q:
		result_node = q.popleft()
		if result_node is None:
			continue
		answer.appendleft(result_node.data)
		if result_node.right is not None:
			q.append(result_node.right)
		if result_node.left is not None:
			q.append(result_node.left)
	return answer


def reverseLevelOrder(root):
	q = []
	res = []
	if not root:
		return []
	q.append(root)
	while len(q) > 0:
		curr = q.pop(0)
		res.append(curr.data)
		if curr.right:
			q.append(curr.right)
		if curr.left:
			q.append(curr.left)
	res.reverse()
	return res