Given a binary tree, find its level order traversal.
Level order traversal of a tree is breadth-first traversal for the tree.
Example 1:
Input:
    1
  /   \ 
 3     2
Output:1 3 2
Example 2:
Input:
        10
     /      \
    20       30
  /   \
 40   60
Output:10 20 30 40 60
Your Task:
You don't have to take any input. Complete the function levelOrder() that takes the root node as input parameter and returns a list of integers containing the level order traversal of the given Binary Tree.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ Number of nodes ≤ 105
1 ≤ Data of a node ≤ 105

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3







class Solution:

    #Function to return the level order traversal of a tree.

    def levelOrder(self,root ):

        # Code here

Solutions:
class Solution:

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


class Solution:

	def levelOrder(self, root):
		q = []
		q.append(root)
		res = []
		while len(q) != 0:
			u = q.pop(0)
			res.append(u.data)
			if u.left is not None:
				q.append(u.left)
			if u.right is not None:
				q.append(u.right)
		return res


class Solution:

	def levelOrder(self, root):
		result = []
		if not root:
			return result
		queue = deque()
		queue.append(root)
		while queue:
			size = len(queue)
			for i in range(size):
				temp = queue.popleft()
				result.append(temp.data)
				if temp.left != None:
					queue.append(temp.left)
				if temp.right != None:
					queue.append(temp.right)
		return result


class Solution:

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


class Solution:

	def levelOrder(self, root):
		q = deque([root])
		ans = []
		while q:
			node = q.popleft()
			ans.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		return ans


class Solution:

	def levelOrder(self, root):
		if root == None:
			return
		stack = []
		res = []
		stack.append(root)
		while len(stack) != 0:
			res.append(stack[0].data)
			node = stack.pop(0)
			if node.left != None:
				stack.append(node.left)
			if node.right != None:
				stack.append(node.right)
		return res


from collections import deque

class Solution:

	def levelOrder(self, node):
		queue = deque()
		queue.append(node)
		return_list = []
		while queue:
			temp = queue.popleft()
			return_list.append(temp.data)
			if temp.left:
				queue.append(temp.left)
			if temp.right:
				queue.append(temp.right)
		return return_list


class Solution:

	def levelOrder(self, root):
		q = deque()
		res = []
		q.append(root)
		while len(q):
			t = q.popleft()
			res.append(t.data)
			if t.left is not None:
				q.append(t.left)
			if t.right is not None:
				q.append(t.right)
		return res


from queue import Queue

class Solution:

	def levelOrder(self, root):
		q = Queue()
		q.put(root)
		ans = list()
		while q.qsize() > 0:
			node = q.get()
			ans.append(node.data)
			if node.left:
				q.put(node.left)
			if node.right:
				q.put(node.right)
		return ans


from collections import deque

class Solution:

	def levelOrder(self, root):
		queue = deque()
		ans = []
		queue.append(root)
		while len(queue) >= 1:
			node = queue.popleft()
			if node.left is not None:
				queue.append(node.left)
			if node.right is not None:
				queue.append(node.right)
			ans.append(node.data)
		return ans


class Solution:

	def levelOrder(self, root):
		a = [root]
		res = []
		while len(a) > 0:
			p = a.pop(0)
			if p.left:
				a.append(p.left)
			if p.right:
				a.append(p.right)
			res.append(p.data)
		return res


class Solution:

	def levelOrder(self, root):
		a = []
		if root == None:
			return root
		a.append(root)
		q = [root.data]
		while len(a) != 0:
			t = a[0]
			if t.left:
				q.append(t.left.data)
				a.append(t.left)
			if t.right:
				q.append(t.right.data)
				a.append(t.right)
			a.pop(0)
		return q


from collections import deque

class Solution:

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


class Solution:

	def levelOrder(self, root):
		if root == None:
			return []
		q = [root]
		ans = []
		while q:
			nod = q.pop(0)
			ans.append(nod.data)
			if nod.left:
				q.append(nod.left)
			if nod.right:
				q.append(nod.right)
		return ans


from collections import deque

class Solution:

	def levelOrder(self, root):
		ans = []
		if root is None:
			return
		queue1 = deque()
		queue2 = deque()
		queue1.append(root)
		while len(queue1) != 0:
			top = queue1[0]
			queue1.popleft()
			ans.append(top.data)
			if top.left is not None:
				queue2.append(top.left)
			if top.right is not None:
				queue2.append(top.right)
			if len(queue1) == 0:
				(queue1, queue2) = (queue2, queue1)
		return ans


class Solution:

	def printCurrentLevel(self, root, level, ans):
		if root is None:
			return
		if level == 1:
			ans.append(root.data)
		elif level > 1:
			self.printCurrentLevel(root.left, level - 1, ans)
			self.printCurrentLevel(root.right, level - 1, ans)

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

	def levelOrder(self, root):
		ans = []
		h = self.height(root)
		for i in range(1, h + 1):
			self.printCurrentLevel(root, i, ans)
		return ans


from collections import deque

class Solution:

	def levelOrder(self, root):
		q = deque()
		q.append(root)
		arr = []
		while len(q) > 0:
			node = q.popleft()
			arr.append(node.data)
			if node.left != None:
				q.append(node.left)
			if node.right != None:
				q.append(node.right)
		return arr


class Solution:

	def levelOrder(self, root):
		ans = []
		queue = [root]
		while queue:
			node = queue.pop(0)
			ans.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		return ans


class Solution:

	def levelOrder(self, root):
		if root is None:
			return []
		queue = [root]
		level_order = []
		while len(queue) > 0:
			node = queue.pop(0)
			level_order.append(node.data)
			if node.left is not None:
				queue.append(node.left)
			if node.right is not None:
				queue.append(node.right)
		return level_order


class Solution:

	def levelOrder(self, root):
		ls = []
		ans = []
		ls.append(root)
		while ls:
			ele = ls.pop(0)
			ans.append(ele.data)
			if ele.left != None:
				ls.append(ele.left)
			if ele.right != None:
				ls.append(ele.right)
		return ans


class Solution:

	def levelOrder(self, root):
		lvl = self.height(root)
		res = []
		for i in range(1, lvl + 1):
			self.lvlorderByHeight(root, i, res)
		return res

	def lvlorderByHeight(self, root, target, res):
		if root == None or target <= 0:
			return
		if target == 1:
			res.append(root.data)
			return
		self.lvlorderByHeight(root.left, target - 1, res)
		self.lvlorderByHeight(root.right, target - 1, res)

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


class Solution:

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


class Solution:

	def levelOrder(self, root):
		if not root:
			return
		q = []
		res = []
		if root:
			q.append(root)
		while q:
			level = []
			size = len(q)
			for i in range(size):
				node = q.pop(0)
				level.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			res.append(level)
		result = []
		for i in res:
			for j in i:
				result.append(j)
		return result


class Solution:

	def levelOrder(self, root):
		if root is None:
			return []
		queue = [root]
		next_queue = []
		level = []
		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)
			for i in level:
				res.append(i)
			queue = next_queue
			next_queue = []
			level = []
		return res


class Solution:

	def levelOrder(self, root):
		level_order = []
		max_height = [0]

		def get_tree_height(root):
			if root is None:
				return 0
			left_height = 1 + get_tree_height(root.left)
			right_height = 1 + get_tree_height(root.right)
			current_height = max(left_height, right_height)
			return current_height
		height = get_tree_height(root)

		def helper(root, level, level_order, target_level):
			if root:
				if level == target_level:
					level_order.append(root.data)
				else:
					helper(root.left, level + 1, level_order, target_level)
					helper(root.right, level + 1, level_order, target_level)
		for target_height in range(height):
			helper(root, 0, level_order, target_height)
		return level_order


class Solution:

	def levelOrder(self, root):
		from collections import deque
		q = deque()
		q.append(root)
		level_order = []
		while len(q) > 0:
			for i in range(len(q)):
				current_node = q.popleft()
				level_order.append(current_node.data)
				if current_node.left:
					q.append(current_node.left)
				if current_node.right:
					q.append(current_node.right)
		return level_order


from collections import deque

class Solution:

	def levelOrder(self, root):
		if root is None:
			return
		q = deque()
		q.append(root)
		ans = []
		while len(q) > 0:
			temp = q.popleft()
			ans.append(temp.data)
			if temp.left is not None:
				q.append(temp.left)
			if temp.right is not None:
				q.append(temp.right)
		return list(ans)


class Solution:

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

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

		def func(root, level):
			if not root:
				return
			if level == 1:
				arr.append(root.data)
				return
			func(root.left, level - 1)
			func(root.right, level - 1)
		h = height(root)
		for i in range(1, h + 1):
			func(root, i)
		return arr


import queue

class Solution:

	def levelOrder(self, root):
		if root is None:
			return None
		q = queue.Queue()
		mylist = []
		q.put(root)
		while not q.empty():
			curr = q.get()
			mylist.append(curr.data)
			if curr.left is not None:
				q.put(curr.left)
			if curr.right is not None:
				q.put(curr.right)
		return mylist


class Solution:

	def levelOrder(self, root):
		q = [root]
		valuelist = []
		l = iter(q)
		root_ = next(l, 'end')
		while root_ != 'end':
			if root_.left:
				q.append(root_.left)
			if root_.right:
				q.append(root_.right)
			valuelist.append(root_.data)
			root_ = next(l, 'end')
		return valuelist


class Solution:

	def levelOrder(self, root):
		res = []
		queue = []
		if root:
			queue.append(root)
		while queue:
			element = queue.pop(0)
			if element.left:
				queue.append(element.left)
			if element.right:
				queue.append(element.right)
			res.append(element.data)
		return res


import queue

class Solution:

	def levelOrder(self, root):
		q = queue.Queue()
		out = []
		if not root:
			return out
		q.put(root)
		while q.qsize():
			node = q.get()
			out.append(node.data)
			if node.left:
				q.put(node.left)
			if node.right:
				q.put(node.right)
		return out


class Solution:

	def levelOrderUtil(self, root, map, level):
		if root:
			self.levelOrderUtil(root.left, map, level + 1)
			self.levelOrderUtil(root.right, map, level + 1)
			if level not in map:
				map[level] = []
			map[level].append(root.data)

	def levelOrder(self, root):
		map = {}
		self.levelOrderUtil(root, map, 0)
		out = []
		for level in range(len(map)):
			out.extend(map[level])
		return out


class Solution:

	def levelOrder(self, root):
		if root is None:
			return []
		visited = []
		queue = [root]
		while queue:
			node = queue.pop(0)
			visited.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		return visited


from collections import deque

class Solution:

	def levelOrder(self, root):
		arr = []
		q = deque([root])
		while q:
			Node = q.popleft()
			arr.append(Node.data)
			if Node.left != None:
				q.append(Node.left)
			if Node.right != None:
				q.append(Node.right)
		return arr


from collections import deque

class Solution:

	def levelOrder(self, root):
		if root:
			q = deque()
			q.append(root)
			while len(q):
				node = q.popleft()
				print(node.data, end=' ')
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return []


from collections import deque

class Solution:

	def levelOrder(self, root):
		q = deque()
		if root is None:
			return
		q.append(root)
		res = []
		while len(q) != 0:
			x = q.popleft()
			res.append(x.data)
			if x.left is not None:
				q.append(x.left)
			if x.right is not None:
				q.append(x.right)
		return res


class Solution:

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


class Solution:

	def levelOrder(self, root):
		queue = deque()
		queue.append(root)
		answer = []
		while queue:
			e = queue.popleft()
			answer.append(e.data)
			if e.left:
				queue.append(e.left)
			if e.right:
				queue.append(e.right)
		return answer


class Solution:

	def levelOrder(self, root):
		temp = []
		l = [root]
		while len(l) > 0:
			x = l.pop(0)
			temp.append(x.data)
			if x.left:
				l.append(x.left)
			if x.right:
				l.append(x.right)
		return temp


class Solution:

	def levelOrder(self, root):
		temp_arr = [[]]

		def levelOrderUtil(root, level):
			if not root:
				return
			if temp_arr[level]:
				temp_arr[level].append(root.data)
			else:
				temp_arr.insert(level, [root.data])
			levelOrderUtil(root.left, level + 1)
			levelOrderUtil(root.right, level + 1)
		levelOrderUtil(root, 0)
		result_arr = []
		for i in range(len(temp_arr)):
			result_arr += temp_arr[i]
		return result_arr


class Solution:

	def levelOrder(self, root):
		l = []

		def height(node):
			if not node:
				return 0
			return max(height(node.left), height(node.right)) + 1

		def traverse(node, level):
			if not node:
				return
			if level == 1:
				l.append(node.data)
			else:
				traverse(node.left, level - 1)
				traverse(node.right, level - 1)
		h = height(root)
		for i in range(1, h + 1):
			traverse(root, i)
		return l


from collections import deque

class Solution:

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

	def levelOrder(self, root):
		res = []
		self.fun(root, 0, res)
		l = []
		for i in res:
			l.extend(i)
		return l


class Solution:

	def levelOrder(self, root):
		queue = [root]
		answer = []
		while queue:
			p = queue.pop(0)
			answer.append(p.data)
			if p.left is not None:
				queue.append(p.left)
			if p.right is not None:
				queue.append(p.right)
		return answer


from collections import deque

class Solution:

	def levelOrder(self, root):
		if root is None:
			return []
		result = []
		queue = deque([root])
		while queue:
			level_length = len(queue)
			current_level = []
			for i in range(level_length):
				node = queue.popleft()
				current_level.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			result.append(current_level)
		return [val for level in result for val in level]


class Solution:

	def levelOrder(self, root):
		temp_list = [root]
		output = []
		while len(temp_list) != 0:
			temp = []
			for node in temp_list:
				output.append(node.data)
				if node.left != None:
					temp.append(node.left)
				if node.right != None:
					temp.append(node.right)
			temp_list = temp
		return output


class Solution:

	def levelOrder(self, root):
		if root == None:
			return None
		q = []
		q.append(root)
		result = []
		while q:
			n = len(q)
			for i in range(0, n):
				node = q.pop(0)
				if node is not None:
					result.append(node.data)
					q.append(node.left if node.left else None)
					q.append(node.right if node.right else None)
		return result


class Solution:

	def levelOrder(self, root):
		q = [root]
		list1 = []
		while q:
			node = q.pop(0)
			list1.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		return list1


from collections import deque

class Solution:

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


import collections
from collections import deque

class Solution:

	def levelOrder(self, root):
		ans = []
		if root is None:
			return ans
		queue = collections.deque()
		queue.append(root)
		while queue:
			currSize = len(queue)
			currList = []
			while currSize > 0:
				currNode = queue.popleft()
				currList.append(currNode.data)
				currSize -= 1
				if currNode.left is not None:
					queue.append(currNode.left)
				if currNode.right is not None:
					queue.append(currNode.right)
			ans.append(currList)
		res = []
		for i in ans:
			res.extend(i)
		return res


class Solution:

	def levelOrder(self, root):
		level = []
		q = []
		q.append(root)
		while q:
			rootnode = q.pop(0)
			level.append(rootnode.data)
			if rootnode.left is not None:
				q.append(rootnode.left)
			if rootnode.right is not None:
				q.append(rootnode.right)
		return level


class Solution:

	def levelOrder(self, root):
		if root is None:
			return
		arr = []
		ans = []
		arr.append(root)
		while len(arr) > 0:
			ans.append(arr[0].data)
			node = arr.pop(0)
			if node.left is not None:
				arr.append(node.left)
			if node.right is not None:
				arr.append(node.right)
		return ans


class Solution:

	def levelOrder(self, root):
		order = []
		queue = []
		queue.append(root)
		while len(queue) > 0:
			temp = queue.pop(0)
			order.append(temp.data)
			if temp.left:
				queue.append(temp.left)
			if temp.right:
				queue.append(temp.right)
		return order


class Solution:

	def levelUtil(self, root, q1):
		if root is None:
			return
		q1.append(root)
		while len(q1) > 0:
			print(q1[0].data, end=' ')
			node = q1.pop(0)
			if node.left is not None:
				q1.append(node.left)
			if node.right is not None:
				q1.append(node.right)

	def levelOrder(self, root):
		if root is None:
			return
		q1 = []
		self.levelUtil(root, q1)
		return q1


class Solution:

	def levelOrder(self, root):
		if root is None:
			return None
		lis = []
		stack = []
		stack.append(root)
		while len(stack) > 0:
			n = len(stack)
			for i in range(n):
				node = stack.pop(0)
				lis.append(node.data)
				if node.left:
					stack.append(node.left)
				if node.right:
					stack.append(node.right)
		return lis


class Solution:

	def levelOrder(self, root):
		l = []
		l.append(root)
		r = []
		while len(l) != 0:
			t = l.pop(0)
			r.append(t.data)
			if t.left != None:
				l.append(t.left)
			if t.right != None:
				l.append(t.right)
		return r


class Solution:

	def levelOrder(self, root):
		ans = []
		s = []
		s.append(root)
		while len(s) != 0:
			curr = s.pop(0)
			ans.append(curr.data)
			if curr.left != None:
				s.append(curr.left)
			if curr.right != None:
				s.append(curr.right)
		return ans


from collections import deque

class Solution:

	def levelOrder(self, root):
		if not root:
			return []
		Q = deque()
		Q.append(root)
		res = []
		while Q:
			curr = Q.popleft()
			res.append(curr.data)
			if curr.left:
				Q.append(curr.left)
			if curr.right:
				Q.append(curr.right)
		return res