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.