Level order traversal line by line

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

You can also try this code with Online C++ Compiler

Run Code

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 tree, Height of binary tree, and Symmetric Binary Tree.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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!