What is Level Order Traversal and implementation

In this blog, we would discuss what is Level Order Traversal and its implementation. In computer science, a level-order traversal is a traversal of a tree in which the nodes are visited in order from top to bottom, and at each level from left to right. This is also known as a breadth-first traversal, as it visits all the nodes at each level before moving on to the next level. A level-order traversal can be used to find the shortest path between two nodes in a tree, as it will always find the path with the fewest number of edges.

 

 

It can also be used to find the maximum or minimum value in a tree, as it will always visit the nodes in order from left to right. To perform a level-order traversal, we can use a queue to keep track of the nodes at each level. We start by enqueuing the root node, and then we dequeue a node and enqueue all of its child nodes. We continue this process until the queue is empty. Here is an example of a level-order traversal of a binary tree:

 

 

 

 

What is Level order traversal?

 

A level order traversal of a tree is a traversal in which the nodes are visited in order from left to right, starting at the root. The level order traversal of a tree is a very powerful tool for traversing and manipulating trees. It is often used in conjunction with other traversals, such as in-order and preorder traversals.  This is a very simple traversal to perform and can be done using a queue.

 

 

To do a level order traversal, we first need to create a queue. We then visit the root node and add its children to the queue. We then visit the next node in the queue and add its children to the queue.  A level order traversal is a very efficient way to visit all of the nodes in a tree. It is also very easy to implement since it can be done using a simple queue.

 

1

/  \

2      3

/  \       \

4    5       6

 

We would enqueue the nodes in the order: 1, 2, 3, 4, 5, 6.

We would dequeue the nodes in the order: 1, 2, 3, 4, 5, 6.

 

 

 

Implementation of Level Order Traversal

 

class Node:

    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None



def printLevelOrder(root):
    # Base Case
    if root is None:
        return
    queue = []

    # Enqueue Root and initialize height
    queue.append(root)

    while(len(queue) > 0):
        print(queue[0].data)
        node = queue.pop(0)
        if node.left is not None:
            queue.append(node.left)

        if node.right is not None:
            queue.append(node.right)


# Driver Program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Level Order Traversal of binary tree is -")
printLevelOrder(root)

 

 

 

Uses of Level Order Traversal

 

 

• The level order traversal can be used to find the shortest path between two nodes in a tree. It can also be used to find the longest path between two nodes in a tree.

 

• The level order traversal can also be used to find the diameter of a tree. The diameter of a tree is the length of the longest path between any two nodes in the tree.

 

• The level order traversal can also be used to find the height of a tree. The height of a tree is the length of the longest path from the root node to any leaf node.

 

• The level order traversal can also be used to find the size of a tree. The size of a tree is the number of nodes in the tree.

 

• The level order traversal can also be used to find the depth of a tree. The depth of a tree is the length of the longest path from the root node to any other node in the tree.

 

 

 

Also, read about post-order traversal and its implementation.