Last Updated : 16 Jun, 2022
Level Order traversal of binary tree is
1 2 3 4 5# 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 answer list 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))
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
60Author: 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