Level Order Binary Tree Traversal in Python

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.

What is Level Order Traversal?

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.

Overview of the Level Order Binary Tree Traversal Algorithm

Suppose that we have been given a tree. To traverse the tree in level order, we will first print the value in the root node, then we will print the value of children of the root node and we will move on to the next level after completing the current level until nodes from each level are printed.

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.

We will process a node and put it’s children to the queue. We will take out the nodes one by one, print them and then put their children into the queue. Here is the algorithm for level order traversal which depicts the entire process.

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.

Implementation of Level order Binary Tree Traversal in python

We will now implement the above algorithm and execute it for following binary tree.

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)

Output:

Printing the level order traversal of the binary tree.
15
10
25
6
14
20
60

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.

Conclusion

In this article, we have seen the underlying concepts behind level order traversal, designed its algorithm and then implemented it. Stay tuned for more informative articles.

Happy learning!