In this lesson, we'll learn about Level Order Traversal, a fundamental concept in Data Structures and Algorithms. This technique is used to visit each node of a binary tree in the order they appear in different levels of the tree. Let's dive in!
Before we start, let's briefly review binary trees. A binary tree is a data structure consisting of nodes, where each node has at most two children: the left child and the right child. The root node is at the top, and the leaves are at the bottom.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = keyLevel Order Traversal is based on Breadth-First Search (BFS), which is an algorithm for traversing or searching tree or graph data structures. It starts at the root and explores all of the nodes at the current depth prior to moving on to nodes at the next depth level.
To implement Level Order Traversal, we'll use a queue to keep track of the nodes at the current depth level and traverse the tree level by level.
def levelOrder(root):
if root is None:
return
# Create an empty queue for BFS
queue = []
# Enqueue Root to the queue
queue.append(root)
while(queue):
# Dequeue a node from the queue
current = queue.pop(0)
# Print the value of the dequeued node
print(current.val, end=" ")
# Enqueue the two children of the dequeued node if they are present
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)Level Order Traversal can be used in various applications such as printing the tree in a level-wise manner, finding the height of a tree, and more.
Which algorithm is used for Level Order Traversal?