Level Order Traversal using Queue
We need to visit the nodes in a lower level before any node in a higher level, this idea is quite similar to that of a queue. Push the nodes of a lower level in the queue. When any node is visited, pop that node from the queue and push the child of that node in the queue.
This ensures that the node of a lower level are visited prior to any node of a higher level.
Below is the Implementation of the above approach:
// C++ program to print level order traversal
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// 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);
}
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree shown in above diagram
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Level Order traversal of binary tree is \n";
printLevelOrder(root);
return 0;
}
// Iterative Queue based C program
// to do level order traversal
// of Binary Tree
#include <stdio.h>
#include <stdlib.h>
#define MAX_Q_SIZE 500
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
struct node {
int data;
struct node* left;
struct node* right;
};
// Function prototypes
struct node** createQueue(int*, int*);
void enQueue(struct node**, int*, struct node*);
struct node* deQueue(struct node**, int*);
// 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);
}
}
// Utility functions
struct node** createQueue(int* front, int* rear)
{
struct node** queue = (struct node**)malloc(
sizeof(struct node*) * MAX_Q_SIZE);
*front = *rear = 0;
return queue;
}
void enQueue(struct node** queue, int* rear,
struct node* new_node)
{
queue[*rear] = new_node;
(*rear)++;
}
struct node* deQueue(struct node** queue, int* front)
{
(*front)++;
return queue[*front - 1];
}
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Driver program to test above functions
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);
return 0;
}
// Iterative Queue based Java program
// to do level order traversal
// of Binary Tree
import java.util.LinkedList;
import java.util.Queue;
// Class to represent Tree node
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
// Class to print Level Order Traversal
class BinaryTree {
Node root;
// 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);
}
}
}
public static void main(String args[])
{
// Creating a binary tree and entering
// the nodes
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(1);
tree_level.root.left = new Node(2);
tree_level.root.right = new Node(3);
tree_level.root.left.left = new Node(4);
tree_level.root.left.right = new Node(5);
System.out.println("Level order traversal of binary tree is - ");
tree_level.printLevelOrder();
}
}
# Python program to print level
# order traversal using Queue
# A node structure
class Node:
# A utility function to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# 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)
# Driver Program to test above function
if __name__ == '__main__':
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)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
// Iterative Queue based C# program
// to do level order traversal
// of Binary Tree
using System;
using System.Collections.Generic;
// Class to represent Tree node
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
// Class to print Level Order Traversal
public class BinaryTree {
Node root;
// 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);
}
}
}
// Driver code
public static void Main()
{
// Creating a binary tree and entering
// the nodes
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(1);
tree_level.root.left = new Node(2);
tree_level.root.right = new Node(3);
tree_level.root.left.left = new Node(4);
tree_level.root.left.right = new Node(5);
Console.WriteLine("Level order traversal "
+ "of binary tree is - ");
tree_level.printLevelOrder();
}
}
// This code contributed by PrinciRaj1992
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// Class to represent a deque (double-ended queue)
class Deque {
constructor() {
this.queue = [];
}
// Method to add an element to the end of the queue
enqueue(item) {
this.queue.push(item);
}
// Method to remove and return the first element of the queue
dequeue() {
return this.queue.shift();
}
// Method to check if the queue is empty
isEmpty() {
return this.queue.length === 0;
}
}
// 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);
}
}
}
// Create a binary tree and enter the nodes
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
// Print the level order traversal of the binary tree
console.log("Level order traversal of binary tree is - ");
printLevelOrder(root);
Output
Level Order traversal of binary tree is 1 2 3 4 5
Time Complexity: O(N) where N is the number of nodes in the binary tree.
Auxiliary Space: O(N) where N is the number of nodes in the binary tree.
Level Order Traversal (Breadth First Search or BFS) of Binary Tree
Level Order Traversal technique is defined as a method to traverse a Tree such that all nodes present in the same level are traversed completely before traversing the next level.
Example:
Input:
Output:
1
2 3
4 5