Level Order Traversal
Level Order Traversal visits all nodes present in the same level completely before visiting the next level.
Algorithm for Level Order Traversal:
LevelOrder(tree)
- Create an empty queue Q
- Enqueue the root node of the tree to Q
- Loop while Q is not empty
- Dequeue a node from Q and visit it
- Enqueue the left child of the dequeued node if it exists
- Enqueue the right child of the dequeued node if it exists
Uses of Level Order:
- Level Order Traversal is mainly used as Breadth First Search to search or process nodes level-by-level.
- Level Order traversal is also used for Tree Serialization and Deserialization.
Code Snippet for Level Order Traversal:
// Iterative method to find height of Binary Tree
void printLevelOrder(Node* root)
{
// Base Case
if (root == NULL)
return;
// Create an empty queue for level order traversal
queue<Node*> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false) {
// Print front of queue and remove it from queue
Node* node = q.front();
cout << node->data << " ";
q.pop();
// Enqueue left child
if (node->left != NULL)
q.push(node->left);
// Enqueue right child
if (node->right != NULL)
q.push(node->right);
}
}
// Given a binary tree, print its nodes in level order
// using array for implementing queue
void printLevelOrder(struct node* root)
{
int rear, front;
struct node** queue = createQueue(&front, &rear);
struct node* temp_node = root;
while (temp_node) {
printf("%d ", temp_node->data);
// Enqueue left child
if (temp_node->left)
enQueue(queue, &rear, temp_node->left);
// Enqueue right child
if (temp_node->right)
enQueue(queue, &rear, temp_node->right);
// Dequeue node and make it temp_node
temp_node = deQueue(queue, &front);
}
}
// Given a binary tree. Print
// its nodes in level order
// using array for implementing queue
void printLevelOrder()
{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
// poll() removes the present head.
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
// Enqueue left child
if (tempNode.left != null) {
queue.add(tempNode.left);
}
// Enqueue right child
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
# Iterative Method to print the
# height of a binary tree
def printLevelOrder(root):
# Base Case
if root is None:
return
# Create an empty queue
# for level order traversal
queue = []
# Enqueue Root and initialize height
queue.append(root)
while(len(queue) > 0):
# Print front of queue and
# remove it from queue
print(queue[0].data, end=" ")
node = queue.pop(0)
# Enqueue left child
if node.left is not None:
queue.append(node.left)
# Enqueue right child
if node.right is not None:
queue.append(node.right)
// Given a binary tree. Print
// its nodes in level order using
// array for implementing queue
void printLevelOrder()
{
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count != 0) {
Node tempNode = queue.Dequeue();
Console.Write(tempNode.data + " ");
// Enqueue left child
if (tempNode.left != null) {
queue.Enqueue(tempNode.left);
}
// Enqueue right child
if (tempNode.right != null) {
queue.Enqueue(tempNode.right);
}
}
}
// Function to perform level order traversal of a binary tree
function printLevelOrder(root) {
// Create a deque to store nodes for traversal
const queue = new Deque();
// Add the root node to the queue
queue.enqueue(root);
// Continue traversal until the queue is empty
while (!queue.isEmpty()) {
// Remove and get the first node from the queue
const tempNode = queue.dequeue();
// Print the data of the current node
console.log(tempNode.data + " ");
// Enqueue the left child if it exists
if (tempNode.left !== null) {
queue.enqueue(tempNode.left);
}
// Enqueue the right child if it exists
if (tempNode.right !== null) {
queue.enqueue(tempNode.right);
}
}
}
Tree Traversal Techniques – Data Structure and Algorithm Tutorials
Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.
Table of Content
- Tree Traversal Meaning
- Tree Traversal Techniques
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal
- Other Tree Traversals
- Frequently Asked Questions (FAQs) on Tree Traversal Techniques