Level Order Traversal – BFS Algorithm

This one is another way of traversing through a binary tree. There are many other ways you can do it. Click here to check.

Level order traversal is a binary tree version of the BFS (Breadth-First Search) algorithm. The concept is simple. I hope you already know about the binary tree. If we visualize a binary tree something like below, we will see some levels there.

                            1                    -> level 0
                          /    \                     
                        2        3               -> level 1
                      /   \    /   \
                     4     5  6     7            -> level 2

As you can see, there are some nodes at each level.

Level  0 = 1
Level 1 = 2, 3
Level 2 = 4, 5, 6, 7

Using this algorithm, we visit all nodes level by level. Most of the time, we will do it from left to right. If we print all the nodes using this algorithm, the output will be 1, 2, 3, 4, 5, 6, 7.

So how can we implement it using code? For that, we will use a data structure, which is Queue. We all know about it. It follows the rule First In First Out (FIFO). Adding something to a Queue is called Enqueue, and removing something is called Dequeue. But I am not going to use those terms here.

                                      1       
                                    /    \                     
                                  2        3 
                                /   \    /   \
                               4     5  6     7

Assume that we have the root (1) of the above binary tree. First, we have to add it to a queue.

        ---------------
Queue     1
        ---------------

Then we will remove it from the Queue. We can print the removed node and do whatever we want. In the meantime, we will add left and right children of it into the Queue.

         ---------------
Queue         3 -> 2        Removed =  1 
         ---------------

Now, we will remove the front node from the Queue. This time it will be 2, which is the left child of the root node. Similarly, we will add left and right children of it into the Queue if it has. If there is no child, we don’t need to add anything to the Queue.

         ---------------
Queue      5 -> 4 -> 3     Removed =  2 
         ---------------

We will continue to do this until the Queue does not get empty. Let’s see the remaining iteration.

          ---------------
Queue     7 -> 6 -> 5 -> 4    Removed =  3
          ---------------

          ---------------
Queue        7 -> 6 -> 5      Removed =  4
          ---------------

          ---------------
Queue        7 -> 6           Removed =  5
          ---------------

          ---------------
Queue        7                Removed =  6
          ---------------

          ---------------
Queue                         Removed =  7
          ---------------

If we print all the removed nodes, we will get the output. That is 1, 2, 3, 4, 5, 6, 7.

Let’s see the implementation in Python.

class TreeNode:
    
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Level Order
def level_order(root):

    # If there is no root node, return None. 
    if root is None:
        return None

    # Initially, we add the root into the queue before the loop. Otherwise, the loop will not run.
    queue = [root]
    
    while queue:
        node = queue.pop()
        print(node.val)
        
        if node.left:
            queue.insert(0, node.left)
        if node.right:
            queue.insert(0, node.right)

I hope you got a minimal idea about this and how to implement this algorithm.

You can try to solve this algorithm-related problem from LeetCode and other problem-solving sites for a better and more in-depth understanding.

Tags: AlgorithmBinary TreeData StructurePythonTree