Level Order Traversal Algorithm
The Level Order Traversal Queue Algorithm is a tree traversal algorithm that visits the nodes in a binary tree in a breadth-first manner, meaning it processes nodes level by level, from left to right. This technique is also known as Breadth-First Search (BFS) traversal, as it visits all the nodes at a particular depth before moving on to the nodes at the next depth level. The algorithm mainly utilizes a queue data structure to keep track of the nodes to be processed at each level.
The algorithm starts by enqueuing the root node of the binary tree. Then, while the queue is not empty, it dequeues the front node, processes (or visits) it, and enqueues its left and right children if they exist. This process continues until the queue becomes empty, which signifies that all the nodes in the tree have been visited. The Level Order Traversal Queue Algorithm is particularly useful in various applications, such as analyzing hierarchical data structures, determining the shortest path in a tree or graph, and solving certain types of tree-based problems.
package DataStructures.Trees;
public class LevelOrderTraversal {
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
// Root of the Binary Tree
Node root;
public LevelOrderTraversal( Node root) {
this.root = root;
}
/* function to print level order traversal of tree*/
void printLevelOrder() {
int h = height(root);
int i;
for (i = 1; i <= h; i++)
printGivenLevel(root, i);
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node root) {
if (root == null)
return 0;
else {
/**
* Return the height of larger subtree
*/
return Math.max(height(root.left), height(root.right)) + 1;
}
}
/* Print nodes at the given level */
void printGivenLevel(Node root, int level) {
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1) {
printGivenLevel(root.left, level - 1);
printGivenLevel(root.right, level - 1);
}
}
}
