Level Order Tree Traversal in Python

Just like we traverse a python dictionary, a list or tuple to access its elements, We can also traverse binary trees to access their elements. There are four tree traversal algorithms namely In-order tree traversal, Pre-order tree traversal, post-order tree traversal, and level order tree traversal. In this article, we will discuss the level order tree traversal algorithm and will implement it in python.

What is Level Order Tree Traversal?

Level order tree traversal algorithm is a breadth-first tree traversal algorithm. It means that while traversing a tree, we first traverse all the elements at the current level before moving to the next level. To understand this concept, Let us consider the following binary search tree.

The level order traversal of the above tree will be as follows.

We will start from the root and print 50. After that we move to next level and print 20 and 53. After this level, we move to another level and print 11, 22, 52, and 78. So, the level order traversal of above tree is 50, 20, 53, 11, 22, 52, 78.

Algorithm for Level Order Tree Traversal

As we have seen that we have to process elements at each level one by one in the level order tree traversal, we can use the following approach. We will start from the root node and will print its value. After that, we will move both children of the root node to a queue. The queue will be used to contain elements that have to be processed next. Each time we process an element, we will put the children of that element into the queue. In this way all the elements at the same level will be pushed into the queue in continuous order and will be processed in the same order. 

The algorithm for level order tree traversal can be formulated as follows.

1. Define a Queue Q to contain the elements.
2. Insert the root into Q.
3. Take out a node from Q.
4. If  the node is empty i.e. None, goto 8.
5. Print the element in the node. 
6. Insert the left child of the current node into Q.
7. Insert the right child of the current node into Q.
8. Check if Q is Empty. If Yes, Stop. else, goto 3.

Implementation of Level Order Tree Traversal Algorithm in Python

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

In the above program, we have first implemented the binary search tree given in the figure. Then We have used the algorithm for level order tree traversal to traverse the binary search tree in Python. As you can observe, The program used a queue to store the data for processing. Also, the elements of the binary search tree have been printed from left to right in the order of their depth in the tree. The root is printed first while the leaf nodes are printed at last.

Conclusion

In this article, we have discussed the level order tree traversal algorithm in Python. Level order tree traversal can be used to find the width of a binary tree in Python. Also, This algorithm has been used to implement various other algorithms that we will discuss later in this series. In next articles, we will implement other tree traversal algorithms such as In-order tree traversal, pre-order tree traversal, and post-order tree traversal algorithm. To learn more about other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.