Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem statement
2.1.
Example
3.
Algorithm
4.
Implementation
5.
Algorithm Complexity
5.1.
Time complexity 
5.2.
Space complexity 
6.
Frequently Asked Questions
6.1.
What is the need for balancing Binary Trees?
6.2.
What are some of the advantages of using binary trees?
6.3.
What are the Binary search algorithm's limitations?
6.4.
What are different possible Traversals for Binary Trees?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Level order traversal line by line

Author SAURABH ANAND
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction 

binary tree is a tree data structure in which each node has a maximum of two offspring, known as the left and right children.

 

Binary tree

 

In this binary tree level order traversal will be as follows.

Level 0:  1

Level 1:  2, 3

Level 2:  3, 4, 6

Problem statement

Print the nodes of a Binary Tree level by level, with each level on a new line.

Example

a) Let’s have a look at this binary tree.

 

In this binary tree level order traversal will be as follows.

Level 0:  12

Level 1:  13, 14

Level 2:  15, 16, 17

Level 3:  15

 

b) Let’s have a look at another binary tree.

In this binary tree level order traversal will be as follows.

Level 0:  12

Level 1:  13, 14

Level 2:  16, 17

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

Here is the algorithm for Level order traversal of binary tree line by line using the queue.

  • Put the root and a null element in the queue first. As a separator, this null element is used.
  • After that, pop from the top of the queue and add its left and right nodes to the queue's end, then print from the queue's top. 
  • Carry on in this manner until the queues are empty.

Implementation

Code for  Level order traversal of binary tree line by line in c++.

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int data;
    struct Node *left, *right;
};
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
void LevelOrderLineByLine(Node * root) {
  if (root == NULL) return;
  queue < Node * > q1;
  q1.push(root);


  while (q1.empty() == false) {
    Node * node = q1.front();
    cout << node -> data << " ";
    q1.pop();
    if (node -> left != NULL)
      q1.push(node -> left);
    if (node -> right != NULL)
      q1.push(node -> right);
  }
}
 
 
 
int main() {
Node* root = newNode(12);
    root->left = newNode(23);
    root->right = newNode(34);
    root->left->left = newNode(43);
    root->left->right = newNode(53);
    
    LevelOrderLineByLine(root);
return 0;
}

 

Output:

 12 23 34 43 53

Algorithm Complexity

Time complexity 

O(n) where n is the number of nodes in a given binary tree.

Space complexity 

The space complexity of a skewed tree is O(n), while the call stack of a balanced tree consumes O(log n) space (i.e., the height of the balanced tree).

Check out this problem - Diameter Of Binary Tree

Frequently Asked Questions

What is the need for balancing Binary Trees?

A balanced binary tree shortens the time required to search through the tree. The search time complexity of a balanced binary tree is O(log n) in the worst case and O(n) in the best case, where n is the number of nodes. Maintaining a balanced tree is advantageous for large trees.

What are some of the advantages of using binary trees?

Data is inserted and erased more quickly in binary trees than in linked lists and arrays. A hierarchical data storage approach is faster than a linked list and also indicates the structural relationship in the data.

What are the Binary search algorithm's limitations?

The limitations of the Binary Search Algorithm are:

  • It uses a recursive approach which requires more stack space.
  • Programming binary search algorithm is difficult and error-prone 
  • The interaction of this algorithm with memory hierarchy (caching) is poor.

What are different possible Traversals for Binary Trees?

The different possible traversals of Binary Tree are level-order traversal, Diagonal traversal etc.

Conclusion

In this article, we have extensively discussed the concept of Level order traversal of binary tree line by line. We started with the introduction of the binary tree, the problem statement of Level order traversal, the example of Level order traversal of binary tree line by line, the algorithm of Level order traversal, and finally concluded with the implementation of Level order traversal.

After reading about the Level order traversal, are you not feeling excited to read/explore more articles on the topic of binary trees? Don't worry; Coding Ninjas has you covered. To learn, see the introduction to a binary treeHeight of binary tree, and Symmetric Binary Tree.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your capacity in coding, you may check out the mock test series and participate in the contests hosted on the Coding Ninjas Studio website. But if you have just started learning and are looking for questions asked by tech giants like Amazon, Microsoft, Google, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

 You may also consider our paid courses to give your career an edge over others!

 Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Level Order Traversal in Spiral Form
Next article
Level order traversal with direction change after every two levels
Live masterclass