Table of Contents
Level Order Traversal:
Level Order traversal is a method of visiting all nodes of a Binary Tree level by level, from top to bottom and left to right. This traversal explores nodes at each level before moving on to the next level.
Consider this Binary Tree:
5
/ \
3 8
/ \ \
2 4 9
The Level Order traversal sequence for this tree would be: 5, 3, 8, 2, 4, 9.
Level Order Traversal in C++
#include <iostream>
#include <queue> // Include the queue library
// Define a node structure for the Binary Tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to perform Level Order traversal
void levelOrderTraversal(Node* root) {
if (root == nullptr)
return;
// Create a queue for level order traversal
std::queue<Node*> q;
// Enqueue the root node
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
// Visit the current node (print its data)
std::cout << current->data << " ";
// Enqueue the left child if it exists
if (current->left)
q.push(current->left);
// Enqueue the right child if it exists
if (current->right)
q.push(current->right);
}
}
int main() {
// Creating the Binary Tree
Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(8);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->right = new Node(9);
// Perform Level Order traversal
std::cout << "Level Order traversal: ";
levelOrderTraversal(root);
return 0;
}
In this code:
- We define a
Nodestructure for the Binary Tree, which holds data, a left child, and a right child. - The
levelOrderTraversalfunction uses a queue to traverse the Binary Tree in Level Order. - We start by enqueueing the root node, then we dequeue nodes and enqueue their children in a loop.
When you run the code, it creates the Binary Tree, performs Level Order traversal, and prints the sequence 5, 3, 8, 2, 4, 9.
Level Order traversal explores nodes level by level, visiting all nodes at a given level before moving to the next level. This traversal order is useful for tasks like breadth-first search, finding the shortest path, or printing the tree in a structured way.