Level Order Traversal Of  A Binary Tree

Introduction

Binary trees are the specialized version of generic trees where every node can have at most only two children named as the left child and right child of a binary tree. We can travel trees in many ways, like pre-order traversal and post-order traversal, but we will learn about level order traversal of Binary trees in this blog.

What is Level order traversal?

In level order traversal, we first visit all the nodes of a previous level before moving on to the next level. Level order traversal is also referred to as Breadth-First search because, in level order traversal, we cover the breadth of a tree first. Let’s understand it better with the below image:

 

Let’s suppose we have the above binary tree with the root node as 1. Then we have to write its level order traversal. To write level order traversal, we have to go level by level. First, write all the nodes present at level 0, then write all nodes present at level 1, and so on ……

Hence the level order traversal of this binary tree will be: 

1, 2, 3, 4, 5, 6, 7

Let’s learn how to code for printing a level order traversal of a binary tree.

Method 1

This approach is not the optimized one but in an interview, you are expected to start from a brute force approach. So before moving on to an optimized approach we should understand this first:

Step 1. Calculate the height of the binary tree, let us denote this by h. The number of different levels in the binary tree will be equal to this height.

Step 2. For every level ‘lvl’ from 1 to h  print the nodes present at lvl. For printing the nodes at the current level lvl we make a recursive call starting from root of the binary tree with lvl as parameter and recursively call the function on left and right child respectively by decreasing the lvl parameter each time we move one step in depth and print the nodes when the current level lvl becomes 1.

Since the call to function is made in order of left and right child respectively, the nodes at each level are printed from left to right.

After this step, you will be having your correct output.

C++ code for level order Traversal

 

#include <bits/stdc++.h>
using namespace std;


//Binary tree class
class node {
   public:
      //data members
      int data;
       node * left;
       node* right;
};


/* Function prototypes */
void printCurrLevel(node * root, int level);
int height(node * node);
node * newNode(int data);


/* Function to print level
order traversal a tree*/
void printLevelOrder(node * root) {
   int h = height(root);
   for (int i = 1; i <= h; i++)
      printCurrLevel(root, i);
}


/* Print nodes at a current level */
void printCurrLevel(node * root, int level) {
   if (root == NULL)
      return;
   if (level == 1)
      cout << root -> data << " ";
   else if (level > 1) {
      //call on left child
      printCurrLevel(root -> left, level - 1);
      //call on right child
      printCurrLevel(root -> right, level - 1);
   }
}


//function to get the height of tree
int height(node * node) {
   if (node == NULL)
      return 0;
   else {
      /* compute the height of each subtree */
      int lheight = height(node -> left);
      int rheight = height(node -> right);


      /* use the larger one */
      if (lheight > rheight) {
         return (lheight + 1);
      } else {
         return (rheight + 1);
      }
   }
}


//This function will help in creating a new node
node * newNode(int data) {
   node * Node = new node();
   Node -> data = data;
   Node -> left = NULL;
   Node -> right = NULL;


   return (Node);
}


int main() {
   node * root = newNode(1);
   root -> left = newNode(2);
   root -> right = newNode(3);
   root -> left -> left = newNode(4);
   root -> left -> right = newNode(5);


   cout << "Printing level order traversal";
   printLevelOrder(root);


   return 0;
}


Output: 

Printing level order traversal
1 2 3 4 5 

Time Complexity

O(N^2) where N refers to the number of nodes in a binary tree. Suppose you got a skewed tree as input then the complexity of printLevelOrder will be O(N)+O(N-1)+....... Which will lead to O(N^2).

Space Complexity: 

O(N) where N refers to the number of nodes in a binary tree. As we are using recursion here, we will be using O(N) space for the call stack.

Method 2. Using Queue for level Order Traversal

This is the optimized approach for the level order traversal of a binary tree.

Here we will make use of queue data structure i.e First In First Out. We first push a node and then its left and right child into the queue in this approach.

Let’s discuss this approach in steps but before that promise me that you will try to code it on your own after going through these steps. Okay, so let’s see the steps:-

Step 1. Take an empty queue and push the root node into the queue.

Step 2. While the queue is non-empty perform the following steps:

  • Pop the front element from the queue and print it.
  • Push the left child and right child of the popped node if they exist into the queue.
     

On the termination of this while loop, you will have the level order traversal as your output.

As promised, have you tried coding it? 

Let’s see my code now:

Java Program for Level Order Traversal

import java.util.Queue;
import java.util.LinkedList;

 
/* Class to represent Tree node */
class Node {
    //data members
    int data;
    Node left, right;

 
    public Node(int item) {
        data = item;
        left = null;
        right = null;
    }
}

 
class BinaryTree {
    Node root;

 
    //printing the node in level order
    void printLevelOrder() {
        Queue < Node > queue = new LinkedList < Node > ();
        queue.add(root);
        while (!queue.isEmpty()) {

 
            //poll will remove the current head
            Node front = queue.poll();
            System.out.print(front.data + " ");

 
            /*This will be adding the left child into the queue */
            if (front.left != null) {
                queue.add(front.left);
            }

 
            /*This will adding the right child in the queue */
            if (front.right != null) {
                queue.add(front.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(11);
        tree_level.root.left = new Node(12);
        tree_level.root.right = new Node(13);
        tree_level.root.left.left = new Node(14);
        tree_level.root.left.right = new Node(15);

 
        System.out.println("Printing the level order traversal ");
        tree_level.printLevelOrder();
    }
}

Output: 

Printing the level order traversal
11 12 13 14 15 

Time Complexity

Time complexity will be O(N), where N is the number of nodes in a binary tree. Since we are visiting each node of the binary tree and putting each node in the queue, the time complexity will be linear.

Space Complexity

The space complexity of this approach will be O(N) where N is the number of nodes in a binary tree. 

We are using a queue to store each one of the binary trees.

Frequently Asked Questions

Ques 1. What is meant by a Binary tree? 
Ans1. A generic tree where each node can have two children at most is known as a binary tree.

Ques 2. What is the other name of Level order traversal?
Ans 2. Level order traversal is also known as Breadth-first search as we cover the breadth of the tree first rather than height.

Ques 3. Can I achieve level order of traversal of a tree without using a queue?
Ans3. Yes, you can as we have discussed in method 1 of this blog. But this will cost you more in terms of time complexity as without a queue your time complexity will be O(N^2).

Ques 4. What is the benefit of using Level order traversal?
Ans4. Level order traversal or Breadth-first search helps you in finding the shortest distance between two nodes.

Ques 5. Can I use stack instead of the queue to get the level order traversal of a binary tree?
Ans 5. No! You have to use queue only because we want to get nodes we have entered first as first output and it can only be achieved using First In First Out property of queue data structure.

Key takeaways:

In this blog, we have discussed all the two approaches for the level order traversal of a binary tree. But remember, the approach discussed using a queue is the most optimized one, and you are expected to come up with this approach in your interviews. One more thing to remember here is that level order traversal is also referred to as Breadth-first search. I hope this blog has helped you in adding some value to your knowledge. Do share it on social media and help us spread this knowledge. 
Happy Coding :)

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think