Given a Binary Tree, your task is to find its level order traversal.
For the below tree the output will be 1 $ 2 3 $ 4 5 6 7 $ 8 $.
          1
       /     \
     2        3
   /    \     /   \
  4     5   6    7
    \
     8
Example 1:
Input:
          1
        /
       4
     /   \
    4     2
Output:1 $ 4 $ 4 2 $
Example 2:
Input:
            10
          /    \
        20      30
     /     \
    40     60
Output: 10 $ 20 30 $ 40 60 $
Your Task:
This is a function problem. You don't need to read input. Just complete the function levelOrder() that takes nodes as parameter and returns level order traversal as a 2D list.
Note: The driver code prints the levels '$' separated.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of edges <= 1000
0 <= Data of a node <= 100

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
'''

#Function to return the level order traversal line by line of a tree.
def levelOrder(root):
    
    # code here

Solutions:
from collections import deque

def levelOrder(root):
	if root == None:
		return None
	queue = []
	ans = []
	queue.append(root)
	while len(queue) > 0:
		count = len(queue)
		temp = []
		while count > 0:
			t = queue.pop(0)
			temp.append(t.data)
			if t.left != None:
				queue.append(t.left)
			if t.right != None:
				queue.append(t.right)
			count -= 1
		ans.append(temp)
	return ans


def levelOrder(root):
	ans = []
	nodes = [root]
	while len(nodes):
		temp = []
		add = []
		for i in nodes:
			if i.left:
				temp.append(i.left)
			if i.right:
				temp.append(i.right)
			add.append(i.data)
		nodes = temp.copy()
		ans.append(add)
	return ans


from queue import Queue

def solve(queue, ans):
	while queue.empty() == False:
		n = queue.qsize()
		levelNodes = []
		for i in range(n):
			node = queue.get()
			levelNodes.append(node.data)
			if node.left != None:
				queue.put(node.left)
			if node.right != None:
				queue.put(node.right)
		ans.append(levelNodes)

def levelOrder(root):
	ans = []
	queue = Queue()
	queue.put(root)
	solve(queue, ans)
	return ans


from queue import Queue

def solve():
	global queue, ans, prevLevel, temp
	while queue.empty() == False:
		(node, level) = queue.get()
		if level == prevLevel:
			temp.append(node.data)
		else:
			ans.append(temp)
			temp = []
			temp.append(node.data)
			prevLevel = level
		if node.left != None:
			queue.put((node.left, level + 1))
		if node.right != None:
			queue.put((node.right, level + 1))

def levelOrder(root):
	global queue, ans, prevLevel, temp
	prevLevel = 0
	ans = []
	temp = []
	queue = Queue()
	queue.put((root, 0))
	solve()
	ans.append(temp)
	return ans


import collections

def levelOrder(root):
	ans = []
	if root is None:
		return ans
	q = collections.deque()
	q.append(root)
	while q:
		length = len(q)
		li = []
		while length > 0:
			node = q.popleft()
			li.append(node.data)
			length -= 1
			if node.left is not None:
				q.append(node.left)
			if node.right is not None:
				q.append(node.right)
		ans.append(li)
	return ans


def levelOrder(root):

	def height(root):
		if root is None:
			return 0
		else:
			l = height(root.left)
			r = height(root.right)
			if l > r:
				return l + 1
			else:
				return r + 1
	l1 = []
	l = []

	def printlvl(root, lvl):
		if root is not None:
			if lvl == 1:
				l.append(root.data)
			else:
				printlvl(root.left, lvl - 1)
				printlvl(root.right, lvl - 1)
	for i in range(1, height(root) + 1):
		printlvl(root, i)
		l1.append(l)
		l = []
	return l1


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


def levelOrder(root):
	q = []
	ans = []
	q.append(root)
	while len(q) != 0:
		n = len(q)
		res = []
		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)
		ans.append(res)
	return ans


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


def levelOrder(root):
	if root is None:
		return []
	queue = [root]
	level = []
	next_queue = []
	res = []
	while queue != []:
		for root in queue:
			level.append(root.data)
			if root.left is not None:
				next_queue.append(root.left)
			if root.right is not None:
				next_queue.append(root.right)
		res.append(level)
		queue = next_queue
		next_queue = []
		level = []
	return res


def levelOrder(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.append([node.data for node in temp])
	return ans


def levelOrder(root):
	(q, ans, arr) = ([], [], [])
	if root is None:
		return
	q.append(root)
	q.append(-1)
	while len(q) > 1:
		temp = q.pop(0)
		if temp == -1:
			ans.append(arr)
			arr = []
			q.append(-1)
		else:
			arr.append(temp.data)
			if temp.left != None:
				q.append(temp.left)
			if temp.right != None:
				q.append(temp.right)
	ans.append(arr)
	return ans


def levelOrder(root):
	if root is None:
		return
	queue = [root]
	res = []
	while queue:
		count = len(queue)
		ans = []
		while count > 0:
			ele = queue.pop(0)
			ans.append(ele.data)
			if ele.left:
				queue.append(ele.left)
			if ele.right:
				queue.append(ele.right)
			count = count - 1
		res.append(ans)
	return res


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


def levelOrder(root):
	ans = []
	if root == None:
		return ans
	q = []
	q.append(root)
	while len(q) > 0:
		size = len(q)
		level = []
		for i in range(size):
			a = q.pop(0)
			if a.left is not None:
				q.append(a.left)
			if a.right is not None:
				q.append(a.right)
			level.append(a.data)
		ans.append(level)
	return ans


def levelOrder(root):
	queue = [root]
	result = []
	while queue:
		size = len(queue)
		levelArr = []
		for i in range(size):
			top = queue.pop(0)
			levelArr.append(top.data)
			if top.left:
				queue.append(top.left)
			if top.right:
				queue.append(top.right)
		result.append(levelArr)
	return result


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


from collections import deque

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


def levelOrder(root):
	if root is None:
		return
	q = []
	ans = []
	q.append(root)
	level = []
	while len(q) > 0:
		l = []
		for node in q:
			l.append(node.data)
			if node.left is not None:
				level.append(node.left)
			if node.right is not None:
				level.append(node.right)
		ans.append(l)
		q = level
		level = []
	return ans


def levelOrder(root):
	level_elements = [root]
	two_d_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)
		two_d_elements_values_list.append(level_elements_list)
		number_of_elements = len(level_elements)
	return two_d_elements_values_list


def levelOrder(root):
	if not root:
		return []
	res = []
	que = deque([root])
	while que:
		k = len(que)
		ans = []
		for i in range(k):
			curr = que.popleft()
			ans.append(curr.data)
			if curr.left:
				que.append(curr.left)
			if curr.right:
				que.append(curr.right)
		res.append(ans)
	return res


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


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

def levelOrder(root):
	l = []
	fun(root, 0, l)
	return l


def levelOrder(root):
	if root == None:
		return []
	l = [root]
	res = []
	while l:
		r = []
		t = []
		for i in l:
			t.append(i.data)
			if i.left != None:
				r.append(i.left)
			if i.right != None:
				r.append(i.right)
		l = r
		if t:
			res.append(t)
	return res


def levelOrder(root):
	levque = [root]
	while levque:
		printlev(levque)
		levque = pushLevel(levque)
	return []

def printlev(que):
	for i in que:
		print(i.data, end=' ')
	print('$', end=' ')
	return

def pushLevel(que):
	levque = []
	for i in que:
		if i.left:
			levque.append(i.left)
		if i.right:
			levque.append(i.right)
	return levque


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


def height(root):
	if root == None:
		return 0
	return 1 + max(height(root.left), height(root.right))

def levelOrder(root):
	len = height(root)
	a = [[root.data]]
	a1 = [[root]]
	b = []
	c = []
	c1 = []
	i = 0
	while i < len - 1:
		if root.left != None:
			b.append(root.left)
			c.append(root.left.data)
			c1.append(root.left)
		if root.right != None:
			b.append(root.right)
			c.append(root.right.data)
			c1.append(root.right)
		if root == a1[-1][-1]:
			a += [c]
			a1 += [c1]
			c = []
			c1 = []
			i += 1
		if b != []:
			root = b.pop(0)
	return a


def levelOrder(root):
	l = []
	q = []
	k = [0]
	m = -1
	q.append(root)
	while q:
		z = q.pop(0)
		x = k.pop(0)
		if m != x:
			m = x
			l.append([])
		l[-1].append(z.data)
		if z.left is not None:
			q.append(z.left)
			k.append(x + 1)
		if z.right is not None:
			q.append(z.right)
			k.append(x + 1)
	return l


def levelOrder(root):
	q = []
	q.append(root)
	res = []
	while q:
		n = len(q)
		tmp = []
		while n > 0:
			node = q.pop(0)
			tmp.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			n -= 1
		res.append(tmp)
	return res


from collections import deque

def levelOrder(root):
	if not root:
		return root
	q = deque()
	q.append(root)
	ans2 = []
	ans = []
	while q:
		for i in range(len(q)):
			temp = q.popleft()
			ans2.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		ans.append(ans2)
		ans2 = []
	return ans


def levelOrder(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)
	return ans


def levelOrder(root):

	def preorder(root, l, d):
		if root is None:
			l -= 1
			return
		if l not in d.keys():
			d[l] = [root.data]
		else:
			d[l].append(root.data)
		preorder(root.left, l + 1, d)
		preorder(root.right, l + 1, d)
	l = 0
	d = {}
	ans = []
	preorder(root, l, d)
	for i in d.keys():
		ans.append(d[i])
	return ans


from collections import deque

def levelOrder(root):
	if root == None:
		return []
	levels = []
	queue = deque()
	queue.append(root)
	while len(queue) > 0:
		inner = []
		n = len(queue)
		for i in range(n):
			item = queue.popleft()
			inner.append(item.data)
			if item.left is not None:
				queue.append(item.left)
			if item.right is not None:
				queue.append(item.right)
		levels.append(inner)
	return levels


def levelOrder(root):
	levels = []
	if root == None:
		return levels

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


def levelOrder(root):
	queue = [root]
	res = []
	while queue:
		level = []
		vals = []
		for i in queue:
			if i == None:
				continue
			vals.append(i.data)
			level.append(i.left)
			level.append(i.right)
		queue = level
		if vals:
			res.append(vals)
	return res


def levelOrder(root):
	l = [root, 'a']
	res = []
	while True:
		w = l.pop(0)
		t = []
		while w != 'a':
			t.append(w.data)
			if w.left != None:
				l.append(w.left)
			if w.right != None:
				l.append(w.right)
			w = l.pop(0)
		res.append(t)
		if l == []:
			return res
		l.append('a')


def levelOrder(root):
	s = [root, None]
	l = [[]]
	while len(s) != 1:
		e = s.pop(0)
		if e == None:
			l.append([])
			s.append(None)
			continue
		l[-1].append(e.data)
		if e.left != None:
			s.append(e.left)
		if e.right != None:
			s.append(e.right)
	return l


def levelOrder(root):
	if not root:
		return []
	q = [root]
	l = [[root.data]]
	while q:
		level_nodes = []
		for _ in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
				level_nodes.append(node.left.data)
			if node.right:
				q.append(node.right)
				level_nodes.append(node.right.data)
		if level_nodes:
			l.append(level_nodes)
	return l


def levelOrder(root):
	if root is None:
		return
	curr_dq = deque([])
	curr_dq.append(root)
	res = []
	temp = []
	i = 0
	while 1:
		temp = []
		length = len(curr_dq)
		if length == 0:
			break
		while length != 0:
			root = curr_dq.popleft()
			temp.append(root.data)
			if root.left is not None:
				curr_dq.append(root.left)
			if root.right is not None:
				curr_dq.append(root.right)
			length -= 1
		res.insert(i, temp)
		i += 1
	return res


def levelOrder(root):
	q = [root]
	list = []
	while q:
		copy = []
		for i in q:
			copy.append(i.data)
		list.append(copy)
		for _ in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	return list


def levelOrder(root):
	from collections import deque
	q = deque()
	q.append(root)
	result = []
	while len(q):
		s = len(q)
		temp = []
		for i in range(s):
			node = q.popleft()
			temp.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		result.append(temp[:])
	return result


def levelOrder(root):
	queue = [root]
	vis = []
	while queue:
		level = []
		for i in range(len(queue)):
			node = queue.pop(0)
			level.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		vis.append(level)
	return vis


def levelOrder(root):
	q = deque()
	vis = []
	q.append(root)
	q.append(None)
	while len(q) > 1:
		node = q.popleft()
		if node == None:
			vis.append(-1)
			q.append(None)
			continue
		vis.append(node.data)
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)
	ans = []
	i = 0
	while i < len(vis):
		temp = []
		while i < len(vis) and vis[i] != -1:
			temp.append(vis[i])
			i += 1
		i += 1
		ans.append(temp)
	return ans


def levelOrder(root):
	q = []
	ans = []
	if root == None:
		return ans
	q.append(root)
	while q:
		n = len(q)
		a = []
		for j in range(n):
			node = q.pop(0)
			a.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		ans.append(a)
	return ans


def lo(root, v, l):
	if root == None:
		return
	if len(v) == l:
		v.append([root.data])
	else:
		v[l].append(root.data)
	lo(root.left, v, l + 1)
	lo(root.right, v, l + 1)

def levelOrder(root):
	v = []
	l = 0
	lo(root, v, l)
	v1 = []
	for i in v:
		k = []
		for j in i:
			k.append(j)
		v1.append(k)
	return v1


from collections import deque

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


def levelOrder(root):
	l = []
	node = []
	res = []
	nextnode = []
	if root == None:
		return []
	node.append(root)
	while node != []:
		for x in node:
			l.append(x.data)
			if x.left != None:
				nextnode.append(x.left)
			if x.right != None:
				nextnode.append(x.right)
		node = nextnode
		nextnode = []
		res.append(l)
		l = []
	return res


def levelOrder(root):
	q = []
	q.append(root)
	res = []
	while len(q):
		n = len(q)
		tmp = []
		for i in range(n):
			f = q.pop(0)
			if f:
				tmp.append(f.data)
			if f.left:
				q.append(f.left)
			if f.right:
				q.append(f.right)
		res.append(tmp)
	return res


def levelOrder(root):
	que = []
	que.append(root)
	res = []
	while len(que) > 0:
		count = len(que)
		temp = []
		for i in range(count):
			curr_node = que.pop(0)
			temp.append(str(curr_node.data))
			if curr_node.left != None:
				que.append(curr_node.left)
			if curr_node.right != None:
				que.append(curr_node.right)
		res.append(temp)
	return res


from queue import Queue

def levelOrder(root):
	ans = []
	if root == None:
		return ans
	q = Queue()
	q.put(root)
	while not q.empty():
		size = q.qsize()
		l = []
		for i in range(size):
			node = q.get()
			if node and node.left:
				q.put(node.left)
			if node and node.right:
				q.put(node.right)
			if node:
				l.append(node.data)
		ans.append(l)
	return ans


import collections

def levelOrder(root):
	q = collections.deque()
	q.append(root)
	ans = []
	while q:
		qLen = len(q)
		temp = []
		for i in range(qLen):
			cur = q.popleft()
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
			temp.append(cur.data)
		ans.append(temp)
	return ans


def levelOrder(root):
	que = deque([root])
	z = []
	while que:
		res = []
		for _ in range(len(que)):
			node = que.popleft()
			if node:
				if node.left:
					que.append(node.left)
				if node.right:
					que.append(node.right)
				res.append(node.data)
		z.append(res)
	return z


from collections import defaultdict

def levelOrder(root):

	def recur(node, level):
		if node is None:
			return
		ans[level].append(str(node.data))
		recur(node.left, level + 1)
		recur(node.right, level + 1)
	ans = defaultdict(list)
	recur(root, 1)
	val = []
	for (key, value) in ans.items():
		val.append(value)
	return val


from collections import deque

def levelOrder(root):
	if not root:
		return []
	result = []
	queue = deque([root])
	while queue:
		level_size = len(queue)
		level_nodes = []
		for _ in range(level_size):
			node = queue.popleft()
			level_nodes.append(str(node.data))
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		result.append(level_nodes)
	return result


from collections import deque

def levelOrder(root):
	queue = deque()
	queue.append(root)
	ans = []
	while queue:
		tmp = []
		l = len(queue)
		for i in range(l):
			x = queue.popleft()
			tmp.append(x.data)
			if x.left:
				queue.append(x.left)
			if x.right:
				queue.append(x.right)
		ans.append(tmp)
	return ans


def levelOrder(root):
	if root == None:
		return
	q = []
	q.append(root)
	c = []
	while len(q) > 0:
		t = []
		n = len(q)
		for i in range(n):
			temp = q.pop(0)
			t.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		c.append(t)
	return c


def levelOrder(root):
	ans = []
	q = []
	if root is None:
		return stack
	q.append(root)
	while len(q) > 0:
		t = []
		dummy_q = []
		while len(q) != 0:
			x = q.pop(0)
			t.append(x.data)
			if x.left is not None:
				dummy_q.append(x.left)
			if x.right is not None:
				dummy_q.append(x.right)
		ans.append(t)
		q = dummy_q
	return ans


def levelOrder(root):
	res = [[root]]
	while len(res[-1]) != 0:
		ans = []
		a = res[-1]
		for i in a:
			if i.left:
				ans.append(i.left)
			if i.right:
				ans.append(i.right)
		for i in range(len(a)):
			res[-1][i] = res[-1][i].data
		res.append(ans)
	return res[:-1]


from collections import deque

def levelOrder(root):
	if not root:
		return []
	q = deque()
	q.append(root)
	res = []
	while len(q) > 0:
		l = len(q)
		dum = []
		for i in range(l):
			k = q.popleft()
			dum.append(k.data)
			if k.left:
				q.append(k.left)
			if k.right:
				q.append(k.right)
		res.append(dum)
	return res


import collections

def levelOrder(root):
	if not root:
		return []
	res = []
	q = collections.deque()
	q.append(root)
	while q:
		a = []
		le = len(q)
		for i in range(le):
			k = q.popleft()
			a.append(k.data)
			if k.left:
				q.append(k.left)
			if k.right:
				q.append(k.right)
		res.append(a)
	return res


def levelOrder(root):
	from collections import deque
	que = deque()
	que.append(root)
	que.append(None)
	ans = []
	while len(que) > 1:
		ele = que.popleft()
		if ele != None:
			ans.append(ele.data)
			if ele.left != None:
				que.append(ele.left)
			if ele.right != None:
				que.append(ele.right)
		else:
			que.append(None)
			ans.append(None)
	ans.append(None)
	result = []
	res = []
	for i in range(len(ans)):
		if ans[i] != None:
			res.append(ans[i])
		else:
			result.append(res)
			res = []
	return result


def levelOrder(root):
	ans = []
	q = []
	q.append(root)
	level = 1
	while q:
		size = len(q)
		temp = []
		while size != 0:
			size -= 1
			curr = q.pop(0)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
			temp.append(curr.data)
		ans.append(temp)
		level += 1
	return ans


def levelOrder(root):
	ans = []
	if root == None:
		return ans
	q = deque()
	q.appendleft(root)
	while len(q):
		l = []
		n = len(q)
		for i in range(1, n + 1):
			el = q.pop()
			l.append(el.data)
			if el.left:
				q.appendleft(el.left)
			if el.right:
				q.appendleft(el.right)
		ans.append(l)
	return ans


from collections import deque

def levelOrder(root):
	if not root:
		return
	res = [[]]
	deq = deque()
	deq.append([root, 1])
	while deq:
		(n, level) = deq.popleft()
		if len(res) < level:
			res.append([])
		res[level - 1].append(n.data)
		if n.left:
			deq.append([n.left, level + 1])
		if n.right:
			deq.append([n.right, level + 1])
	return res


def levelOrder(root):
	queue = []
	t = []
	queue.append(root)
	while queue != []:
		t2 = []
		for i in range(len(queue)):
			curr = queue[0]
			t2.append(curr.data)
			if curr.left != None:
				queue.append(curr.left)
			if curr.right != None:
				queue.append(curr.right)
			queue.pop(0)
		t.append(t2)
	return t


def levelOrder(root):
	if not root:
		return []
	queue = [root]
	levels = []
	while queue:
		level_size = len(queue)
		level_nodes = []
		for i in range(level_size):
			node = queue.pop(0)
			level_nodes.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		levels.append(level_nodes)
	return levels


def levelOrder(root):
	bfs = []
	if root is None:
		return bfs
	q = deque([])
	q.append(root)
	while q:
		lvl_size = len(q)
		curr_lvl = []
		for i in range(lvl_size):
			curr = q.popleft()
			curr_lvl.append(curr.data)
			if curr.left is not None:
				q.append(curr.left)
			if curr.right is not None:
				q.append(curr.right)
		bfs.append(curr_lvl)
	return bfs


class Node:

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

def levelOrder(root):
	if root == None:
		return None
	queue = []
	ans = []
	queue.append(root)
	while len(queue) > 0:
		count = len(queue)
		temp = []
		while count > 0:
			t = queue.pop(0)
			temp.append(t.data)
			if t.left != None:
				queue.append(t.left)
			if t.right != None:
				queue.append(t.right)
			count -= 1
		ans.append(temp)
	return ans


def levelOrder(root):
	result = [[root.data]]
	ans = []
	queue = [root]
	while queue:
		n = len(queue)
		for i in range(n):
			x = queue.pop(0)
			if x.left:
				ans.append(x.left.data)
				queue.append(x.left)
			if x.right:
				ans.append(x.right.data)
				queue.append(x.right)
		if ans:
			result.append(ans)
		ans = []
	return result


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


import collections

def levelOrder(root):
	q = collections.deque()
	q.append(root)
	size = 1
	ans = []
	while size > 0:
		cur = size
		cur_level = []
		for i in range(cur):
			elem = q.popleft()
			size -= 1
			cur_level.append(elem.data)
			if elem.left:
				q.append(elem.left)
				size += 1
			if elem.right:
				q.append(elem.right)
				size += 1
		ans.append(cur_level)
	return ans


def levelOrder(root):
	if not root:
		return
	queue = [root]
	res = []
	while queue:
		level = []
		for i in range(len(queue)):
			currNode = queue.pop(0)
			level.append(currNode.data)
			if currNode.left:
				queue.append(currNode.left)
			if currNode.right:
				queue.append(currNode.right)
		res.append(level)
	return res


def levelOrder(root):
	d = []
	q = []
	g = {}
	d.append(root)
	q.append(0)
	while len(d) > 0:
		c = d.pop(0)
		m = q.pop(0)
		if m not in g:
			g[m] = [c.data]
		else:
			g[m].append(c.data)
		if c.left != None:
			d.append(c.left)
			q.append(m + 1)
		if c.right != None:
			d.append(c.right)
			q.append(m + 1)
	l = [[]]
	for x in g:
		l.append(g[x])
	l.pop(0)
	return l


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


def levelOrder(root):
	if root == None:
		return
	q = [root]
	l = []
	specl = '$'
	ans = []
	while q:
		l = []
		s = len(q)
		for i in range(len(q)):
			t = q.pop(0)
			if t:
				l.append(t.data)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
		if l:
			ans.append(l)
	ans.append(specl)
	return ans[:len(ans) - 1]


def lvl(root, x, lst):
	if root == None:
		return lst
	if x == 0:
		lst.append(root.data)
	lst = lvl(root.left, x - 1, lst)
	lst = lvl(root.right, x - 1, lst)
	return lst

def ht(root):
	if root == None:
		return -1
	return max(ht(root.left), ht(root.right)) + 1

def levelOrder(root):
	a = ht(root)
	l = []
	for x in range(a + 1):
		l.append(lvl(root, x, []))
	return l


def levelOrder(root):
	lis = []
	q = []
	q.append(root)
	q.append(None)
	x = []
	while len(q):
		temp = q.pop(0)
		if temp == None:
			lis.append(x)
			if len(q) == 0:
				break
			q.append(None)
			x = []
		else:
			x.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
	return lis


def levelOrder(root):
	ans = []
	queue = [root]
	level = []
	while queue != [] and root is not None:
		l = []
		for node in queue:
			l.append(node.data)
			if node.left:
				level.append(node.left)
			if node.right:
				level.append(node.right)
		ans.append(l)
		queue = level
		level = []
	return ans


def levelOrder(root):
	if not root:
		return
	ans = []
	nodes = []
	nodes.append(root)
	while nodes:
		l = len(nodes)
		res = []
		while l:
			cur = nodes.pop(0)
			res.append(cur.data)
			if cur.left:
				nodes.append(cur.left)
			if cur.right:
				nodes.append(cur.right)
			l -= 1
		ans.append(res)
	return ans


def levelOrder(root):
	if root == None:
		return
	q = [root]
	lis = []
	ans = []
	while q:
		lis = []
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			lis.append(node.data)
		ans.append(lis)
	return ans


import collections

def levelOrder(root):
	d = []
	queue = collections.deque([root])
	level_traverse(queue, d)
	return d

def level_traverse(queue, d):
	while len(queue):
		n = len(queue)
		l = []
		while n:
			temp = queue.popleft()
			l.append(temp.data)
			if temp.left is not None:
				queue.append(temp.left)
			if temp.right is not None:
				queue.append(temp.right)
			n -= 1
		d.append(l)


def levelOrder(root):
	A = []
	B = []
	C = []
	D = []
	if root is None:
		return A
	A.append(root)
	while len(A) > 0:
		while len(A) > 0:
			node = A.pop(0)
			B.append(node.data)
			if node.left is not None:
				D.append(node.left)
			if node.right is not None:
				D.append(node.right)
		A.extend(D)
		D = []
		C.append(B)
		B = []
	return C


def levelOrder(root):
	a = []
	res = []
	if root is None:
		return
	q = deque()
	q.append(root)
	while len(q) > 0:
		n = len(q)
		a = []
		for i in range(n):
			node = q.popleft()
			a.append(node.data)
			if node.left is not None:
				q.append(node.left)
			if node.right is not None:
				q.append(node.right)
		res.append(a)
	return res


def levelOrder(root):

	def height(node):
		if node is None:
			return 0
		else:
			lheight = height(node.left)
			rheight = height(node.right)
			if lheight > rheight:
				return lheight + 1
			else:
				return rheight + 1

	def currlvl(root, lvl):
		if root is None:
			return
		elif lvl == 1:
			res.append(root.data)
		elif lvl > 1:
			currlvl(root.left, lvl - 1)
			currlvl(root.right, lvl - 1)
	res = []
	l = []
	h = height(root)
	for i in range(1, h + 1):
		currlvl(root, i)
		l.append(res)
		res = []
	return l


def levelOrder(root):
	res = []
	if root == None:
		return res
	from collections import deque
	q = deque()
	q.append(root)
	q.append(None)
	l = []
	while len(q) > 1:
		curr = q.popleft()
		if curr == None:
			q.append(None)
			res.append(l)
			l = []
			continue
		l.append(curr.data)
		if curr.left != None:
			q.append(curr.left)
		if curr.right != None:
			q.append(curr.right)
	res.append(l)
	return res


def levelOrder(root):
	ans = []
	a = [root]
	b = []
	counter = 0
	i = 0
	while 1:
		if counter == 0:
			if len(a) == 0:
				break
			elif i < len(a):
				temp = a[i]
				if temp.left != None:
					b.append(temp.left)
				if temp.right != None:
					b.append(temp.right)
				a[i] = a[i].data
				i += 1
			else:
				counter = 1
				ans.append(a)
				a = []
				i = 0
		elif len(b) == 0:
			break
		elif i < len(b):
			temp = b[i]
			if temp.left != None:
				a.append(temp.left)
			if temp.right != None:
				a.append(temp.right)
			b[i] = b[i].data
			i += 1
		else:
			counter = 0
			ans.append(b)
			b = []
			i = 0
	return ans


def levelOrder(root):
	res = []
	L = []
	if root is None:
		return
	L.append(root)
	while len(L) > 0:
		n = len(L)
		level = []
		for i in range(n):
			elem = L.pop(0)
			level.append(elem.data)
			if elem.left is not None:
				L.append(elem.left)
			if elem.right is not None:
				L.append(elem.right)
		res.append(level)
	return res


def levelOrder(root):
	res = []
	queue = []
	queue.append(root)
	i = 0
	while queue:
		q_len = len(queue)
		temp = []
		while q_len > 0:
			q_len -= 1
			node = queue.pop(0)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			temp.append(node.data)
		res.append(temp)
	return res


def levelOrder(root):
	q = []
	c = []
	h = []
	j = 0
	if len(q) == 0:
		q.append(root)
	k = root.data
	h += str(k)
	while len(q) > 0:
		h = []
		for i in range(len(q)):
			root = q[0]
			h.append(root.data)
			q.remove(q[0])
			if root.left != None:
				q.append(root.left)
			if root.right != None:
				q.append(root.right)
		c.append(h)
	return c


def levelOrder(root):
	if not root:
		return None
	q = deque()
	q.append(root)
	ans = []
	while q:
		n = len(q)
		l = []
		while n > 0:
			temp = q.popleft()
			l.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
			n -= 1
		ans.append(l)
	return ans


def height(root):
	if root:
		return max(height(root.left), height(root.right)) + 1
	else:
		return 0

def returnLevel(root, lvl):
	if root is None:
		return []
	if lvl == 1:
		return [root.data]
	elif lvl > 1:
		return_lst = []
		return_lst += returnLevel(root.left, lvl - 1)
		return_lst += returnLevel(root.right, lvl - 1)
		return return_lst

def levelOrder(root):
	h = height(root)
	lvl_order_traversal = []
	for lvl in range(1, h + 1):
		lvl_order_traversal.append(returnLevel(root, lvl))
	return lvl_order_traversal