Level Order Traversal using Queue

How does Level Order Traversal work?

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++

// 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;
}

Java

// 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

# 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

Javascript

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

Tags:

#Amazon #Cisco #D-E-Shaw #Flipkart #Microsoft #Morgan Stanley #Ola Cabs #Payu #Qualcomm #Samsung #tree-level-order #DSA #Queue #Tree #Amazon #Cisco #D-E-Shaw #Flipkart #Microsoft #Morgan Stanley #Ola Cabs #Payu #Qualcomm #Samsung #Queue #Tree

How does Level Order Traversal work?

Level Order Traversal using Queue

Level Order Traversal (Breadth First Search or BFS) of Binary Tree

Similar Reads