# binary tree level order traversal in python

• Last Update :
• Techknowledgy :

Last Updated : 16 Jun, 2022

```Level Order traversal of binary tree is
1 2 3 4 5```

Suggestion : 2
```# To
import queue datastructure
import collections

# Code to implement a binary tree
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

# Function
for level Order Traversal
def levelOrderTraversal(root):
ans = []

# Return Null
if the tree is empty
if root is None:
return ans

# Initialize queue
queue = collections.deque()
queue.append(root)

# Iterate over the queue until it 's empty
while queue:
# Check the length of queue
currSize = len(queue)
currList = []

while currSize > 0:
# Dequeue element
currNode = queue.popleft()
currList.append(currNode.val)
currSize -= 1

# Check
for left child
if currNode.left is not None:
queue.append(currNode.left)
# Check
for right child
if currNode.right is not None:
queue.append(currNode.right)

# Append the currList to answer after each iteration
ans.append(currList)

return ans

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Check
if the algorithm work
print(levelOrderTraversal(root))```

Suggestion : 3

Level order traversal is a breadth-first binary tree traversal technique. We first traverse a node. Then, we traverse all the neighbor nodes in the present depth prior to moving on to the nodes in the next level of the tree and thus named level order traversal.,In the above code, first we have constructed the binary tree given in the image and then we have printed the level order traversal of the binary tree.,In this article, we will learn about the level order binary tree traversal. First We will look at the underlying concepts behind level order traversal and then we will implement level order traversal for binary trees in python.,So, we have mainly the task of printing the nodes in the current level of the tree starting from 1st level to last level. To implement this concept we will use first in first out technique i.e. queue to process the tree.

```Algorithm LevelOrder:
Input: Root of the tree.
Output: Prints the binary tree in level order traversal.
Start.
1. If the root is empty,
return.
2. Let Q be a queue.
3. Insert root into the Q.
4. Take out a node from Q.
5. If the node is empty, goto 9.
6. Print the node.
7. Insert left child of the node into Q.
8. Insert the right child of the node into Q.
9. Check
if Q is empty.If Q is not empty, goto 4.
Stop.```
```from queue
import Queue
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None

def insert(root, newValue):
#if binary search tree is empty, make a new node and declare it as root
if root is None:
root = BinaryTreeNode(newValue)
return root
#binary search tree is not empty, so we will insert it into the tree
#if newValue is less than value of data in root, add it to left subtree and proceed recursively
if newValue < root.data:
root.leftChild = insert(root.leftChild, newValue)
else:
#if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild = insert(root.rightChild, newValue)
return root
def levelorder(root):
if root == None:
return
Q = Queue()
Q.put(root)
while (not Q.empty()):
node = Q.get()
if node == None:
continue
print(node.data)
Q.put(node.leftChild)
Q.put(node.rightChild)

root = insert(None, 15)
insert(root, 10)
insert(root, 25)
insert(root, 6)
insert(root, 14)
insert(root, 20)
insert(root, 60)
print("Printing the level order traversal of the binary tree.")
levelorder(root)```
```Printing the level order traversal of the binary tree.
15
10
25
6
14
20
60```

Suggestion : 4

Author: Aditya Raj Last Updated: September 14, 2021

Now we will implement the above algorithm in python. After that, we will process the binary search tree used in the above example using the same algorithm.

```from queue
import Queue

class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None

def levelorder(root):
Q = Queue()
Q.put(root)
while (not Q.empty()):
node = Q.get()
if node == None:
continue
print(node.data)
Q.put(node.leftChild)
Q.put(node.rightChild)

def insert(root, newValue):
#
if binary search tree is empty, create a new node and declare it as root
if root is None:
root = BinaryTreeNode(newValue)
return root
#
if newValue is less than value of data in root, add it to left subtree and proceed recursively
if newValue < root.data:
root.leftChild = insert(root.leftChild, newValue)
else:
#
if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild = insert(root.rightChild, newValue)
return root

root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Level Order traversal of the binary tree is:")
levelorder(root)```

Output:

```Level Order traversal of the binary tree is:
50
20
53
11
22
52
78```