Level order traversal line by line | Set 3 (Using One Queue)

Last Updated : 21 Dec, 2022

Given a Binary Tree, print the nodes level-wise, each level on a new line.

Example

Output:
1
2 3
4 5

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

We have discussed two solutions in the articles below.
Print level order traversal line by line | Set 1
Level order traversal line by line | Set 2 (Using Two Queues)
In this post, a different approach using one queue is discussed. First insert the root and a null element into the queue. This null element acts as a delimiter. Next, pop from the top of the queue and add its left and right nodes to the end of the queue and then print at the top of the queue. Continue this process till the queues become empty.

C++

/* C++ program to print levels 
line by line */
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct node
{
    struct node *left;
    int data;
    struct node *right;
};
 
// Function to do level order
// traversal line by line
void levelOrder(node *root)
{
    if (root == NULL) return;
 
    // Create an empty queue for
    // level order traversal
    queue<node *> q;
     
    // to store front element of 
    // queue.
    node *curr;
 
    // Enqueue Root and NULL node.
    q.push(root);
    q.push(NULL);
 
    while (q.size() > 1)
    {
        curr = q.front();
        q.pop();
         
        // condition to check 
        // occurrence of next 
        // level.
        if (curr == NULL)
        {
           q.push(NULL);
           cout << "\n";
        }
         
        else {
             
            // pushing left child of 
            // current node.
            if(curr->left)
            q.push(curr->left);
             
            // pushing right child of
            // current node.
            if(curr->right)
            q.push(curr->right);
             
            cout << curr->data << " ";
        }
    }
}
 
// Utility function to create a
// new tree node
node* newNode(int data)
{
    node *temp = new node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
// Driver program to test above
// functions
int main()
{
     
    // Let us create binary tree
    // shown above
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);
 
    levelOrder(root);
    return 0;
}
 
// This code is contributed by
// Nikhil Jindal.

Java

// Java program to do level order
// traversal line by line
import java.util.LinkedList;
import java.util.Queue;
 
public class GFG {
  static class Node {
    int data;
    Node left;
    Node right;
 
    Node(int data) {
      this.data = data;
      left = null;
      right = null;
    }
  }
 
  // Prints level order traversal line
  // by line using two queues.
  static void levelOrder(Node root) {
    if (root == null)
      return;
 
    Queue<Node> q = new LinkedList<>();
 
    // Pushing root node into the queue.
    q.add(root);
 
    // Pushing delimiter into the queue.
    q.add(null);
 
    // Executing loop till queue becomes
    // empty
    while (!q.isEmpty()) {
 
      Node curr = q.poll();
 
      // condition to check the
      // occurrence of next level
      if (curr == null) {
        if (!q.isEmpty()) {
          q.add(null);
          System.out.println();
        }
      } else {
        // Pushing left child current node
        if (curr.left != null)
          q.add(curr.left);
 
        // Pushing right child current node
        if (curr.right != null)
          q.add(curr.right);
 
        System.out.print(curr.data + " ");
      }
    }
  }
 
  // Driver function
  public static void main(String[] args) {
 
    Node 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);
    root.right.right = new Node(6);
 
    levelOrder(root);
  }
}
 
// This code is Contributed by Rishabh Jindal

Python3

# Python3 program to print levels
# line by line
from collections import deque as queue
 
# A Binary Tree Node
 
 
class Node:
 
    def __init__(self, key):
 
        self.data = key
        self.left = None
        self.right = None
 
# Function to do level order
# traversal line by line
 
 
def levelOrder(root):
 
    if (root == None):
        return
 
    # Create an empty queue for
    # level order traversal
    q = queue()
 
    # To store front element of
    # queue.
    #node *curr
 
    # Enqueue Root and None node.
    q.append(root)
    q.append(None)
 
    while (len(q) > 1):
        curr = q.popleft()
        # q.pop()
 
        # Condition to check
        # occurrence of next
        # level.
        if (curr == None):
            q.append(None)
            print()
 
        else:
 
            # Pushing left child of
            # current node.
            if (curr.left):
                q.append(curr.left)
 
            # Pushing right child of
            # current node.
            if (curr.right):
                q.append(curr.right)
 
            print(curr.data, end=" ")
 
 
# Driver code
if __name__ == '__main__':
 
    # Let us create binary tree
    # shown above
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(6)
 
    levelOrder(root)
 
# This code is contributed by mohit kumar 29

C#

// C# program to do level order
// traversal line by line
using System;
using System.Collections;
 
class GFG 
{
public class Node 
{
    public int data;
    public Node left;
    public Node right;
 
    public Node(int data) 
    {
        this.data = data;
        left = null;
        right = null;
    }
}
 
// Prints level order traversal line
// by line using two queues.
static void levelOrder(Node root) 
{
    if (root == null)
    return;
 
    Queue q = new Queue();
 
    // Pushing root node into the queue.
    q.Enqueue(root);
 
    // Pushing delimiter into the queue.
    q.Enqueue(null);
 
    // Executing loop till queue becomes
    // empty
    while (q.Count>0)
    {
 
        Node curr = (Node)q.Peek();
        q.Dequeue();
 
        // condition to check the
        // occurrence of next level
        if (curr == null) 
        {
            if (q.Count > 0)
            {
                q.Enqueue(null);
                 Console.WriteLine();
            }
        } 
        else
        {
            // Pushing left child current node
            if (curr.left != null)
            q.Enqueue(curr.left);
     
            // Pushing right child current node
            if (curr.right != null)
            q.Enqueue(curr.right);
     
            Console.Write(curr.data + " ");
        }
    }
}
 
// Driver code
static public void Main(String []args) 
{
 
    Node 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);
    root.right.right = new Node(6);
 
    levelOrder(root);
}
}
 
// This code is Contributed by Arnab Kundu

Javascript

<script>
 
// Javascript program to do level order
// traversal line by line
class Node
{
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// Prints level order traversal line
// by line using two queues.
function levelOrder(root)
{
    if (root == null)
      return;
  
    let q= [];
  
    // Pushing root node into the queue.
    q.push(root);
  
    // Pushing delimiter into the queue.
    q.push(null);
  
    // Executing loop till queue becomes
    // empty
    while (q.length!=0) {
  
      let curr = q.shift();
  
      // condition to check the
      // occurrence of next level
      if (curr == null) {
          if (q.length!=0) {
          q.push(null);
          document.write("<br>");
        }
      } 
      else {
        // Pushing left child current node
        if (curr.left != null)
          q.push(curr.left);
  
        // Pushing right child current node
        if (curr.right != null)
          q.push(curr.right);
  
        document.write(curr.data + " ");
      }
    }
}
 
// Driver function
let 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);
root.right.right = new Node(6);
 
levelOrder(root);
 
 
 
// This code is contributed by patel2127
</script>

Output

1 
2 3 
4 5 6

Time Complexity: O(n)
Auxiliary Space: O(n) for queue, where n is no of nodes of binary tree

R

rishabh jindal 1

Improve

Previous Article

Islands in a graph using BFS

Find the first non-repeating character from a stream of characters

Similar Reads

Level order traversal in spiral form | Using one stack and one queue

Write a function to print spiral order traversal of a tree. For below tree, function should print 1, 2, 3, 4, 5, 6, 7. You are allowed to use only one stack. We have seen recursive and iterative solutions using two stacks . In this post, a solution with one stack and one queue is discussed. The idea is to keep on entering nodes like normal level or

Pre Order, Post Order and In Order traversal of a Binary Tree in one traversal | (Using recursion)

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order in one iteration. Examples: Input: Output: Pre Order: 1 2 4 5 3 6 7 Post Order: 4 5 2 6 7 3 1 In Order: 4 2 5 1 6 3 7 Input: Output: Pre Order: 1 2 4 8 12 5 9 3 6 7 10 11 Post Order: 12 8 4 9 5 2 6 10 11 7 3 1 In Order: 8 12 4 2 9 5 1 6

Level order traversal line by line | Set 2 (Using Two Queues)

Given a Binary Tree, print the nodes level wise, each level on a new line. Output: 1 2 3 4 5Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. We have discussed one solution in below article. Print level order traversal line by line | Set 1 In this post, a different approach using two queues is discussed. We can ins

Print level order traversal line by line | Set 1

Given root of a binary tree, The task is to print level order traversal in a way that nodes of all levels are printed in separate lines. Examples: Input: Output: 208 224 1210 14 Input: 1 / \ 2 3 / \ 4 5 Output: 12 34 5 Recommended PracticeLevel order traversal Line by LineTry It! Note: that this is different from simple level order traversal where

Level order traversal of Binary Tree using Morris Traversal

Given a binary tree, the task is to traverse the Binary Tree in level order fashion.Examples: Input: 1 / \ 2 3 Output: 1 2 3 Input: 5 / \ 2 3 \ 6 Output: 5 2 3 6 Approach: The idea is to use Morris Preorder Traversal to traverse the tree in level order traversal.Observations: There are mainly two observations for the traversal of the tree using Mor

Print a Binary Tree in Vertical Order | Set 3 (Using Level Order Traversal)

Given a binary tree, print it vertically. The following example illustrates vertical order traversal. 1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 The output of print this tree vertically will be: 4 2 1 5 6 3 8 7 9 We have discussed an efficient approach in below post.Print a Binary Tree in Vertical Order | Set 2 (Hashmap based Method)The above solution uses

Connect Nodes at same Level (Level Order Traversal)

Write a function to connect all the adjacent nodes at the same level in a binary tree. Example: Input Tree A / \ B C / \ \ D E F Output Tree A--->NULL / \ B-->C-->NULL / \ \ D-->E-->F-->NULL We have already discussed O(n^2) time and O approach in Connect nodes at same level as morris traversal in worst case can be O(n) and calling

Flatten Binary Tree in order of Level Order Traversal

Given a Binary Tree, the task is to flatten it in order of Level order traversal of the tree. In the flattened binary tree, the left node of all the nodes must be NULL.Examples: Input: 1 / \ 5 2 / \ / \ 6 4 9 3 Output: 1 5 2 6 4 9 3 Input: 1 \ 2 \ 3 \ 4 \ 5 Output: 1 2 3 4 5 Approach: We will solve this problem by simulating the Level order travers

Insertion in n-ary tree in given order and Level order traversal

Given a set of parent nodes where the index of the array is the child of each Node value, the task is to insert the nodes as a forest(multiple trees combined together) where each parent could have more than two children. After inserting the nodes, print each level in a sorted format. Example: Input: arr[] = {5, 3, -1, 2, 5, 3} Output:-1 231 5Input:

Print nodes of a Binary Search Tree in Top Level Order and Reversed Bottom Level Order alternately

Given a Binary Search Tree, the task is to print the nodes of the BST in the following order: If the BST contains levels numbered from 1 to N then, the printing order is level 1, level N, level 2, level N - 1, and so on.The top-level order (1, 2, …) nodes are printed from left to right, while the bottom level order (N, N-1, ...) nodes are printed f

Article Tags :

Practice Tags :