Level Order Traversal Line Set 3 Using One Queue

Last Updated on December 14, 2022 by Prepbytes

Problem Statement:

Given a binary tree, print the nodes level by level or level wise and each level on a new line.

Queue

A queue is basically a linear data structure that works on the principle of FIFO (First in First out) which means an element that is enqueued first will be dequeued first. Element is enqueued from the rear end of the queue and dequeued from the front end. The insertion operation in the queue is known as enqueue and the deletion operation in the queue is known as dequeue.
The queue is used when the operations are to be performed in the manner of First in First out order just like Breadth-First Search.

For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.

Basic Operations of Queue:

• Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).

• Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).

• Front: This function returns the front element of the queue. The time complexity of this function is O(1).

• Rear: This function returns the last element of the queue. The time complexity of this function is O(1).

• Peek(): This operation is used to get the value of the element from the front of the queue.

What is a Binary Tree?

Binary tree is a type of Tree data structure in which every node in the tree will have 2 or less than 2 child nodes and those child nodes will be termed as the left child and the right child of the node.

Example of Binary Tree:

Level order traversal: we have given a binary tree and we have to print the order level by level i.e level wise and print each level on a new line.

Output: 1
2 3
4 5

Approach: First we’ll insert the root node and a null element into the queue and this null element will act as a delimiter. Next pop from the top of the queue and its left and right nodes to the end of the queue and then print the top of the queue, continue this process until the queue will become empty.

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

struct node
{
	struct node *left;
	int data;
	struct node *right;
};

void levelOrder(node *root)
{
	if (root == NULL) return;

	queue<node *> q;
	
	node *curr;

	q.push(root);
	q.push(NULL);

	while (q.size() > 1)
	{
		curr = q.front();
		q.pop();
		
		if (curr == NULL)
		{
		q.push(NULL);
		cout << "\n";
		}
		
		else {
			
			if(curr->left)
			q.push(curr->left);
			
			if(curr->right)
			q.push(curr->right);
			
			cout << curr->data << " ";
		}
	}
}

node* newNode(int data)
{
	node *temp = new node;
	temp->data = data;
	temp->left = NULL;
	temp->right = NULL;
	return temp;
}

int main()
{
	
	node *root = newNode(10);
	root->left = newNode(20);
	root->right = newNode(30);
	root->left->left = newNode(40);
	root->left->right = newNode(50);
	root->right->right = newNode(60);

	levelOrder(root);
	return 0;
}

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

class PrepBytes {
static class Node {
	int data;
	Node left;
	Node right;

	Node(int data) {
	this.data = data;
	left = null;
	right = null;
	}
}

static void levelOrder(Node root) {
	if (root == null)
	return;

	Queue<Node> q = new LinkedList<>();

	q.add(root);

	q.add(null);

	while (!q.isEmpty()) {

	Node curr = q.poll();

	if (curr == null) {
		if (!q.isEmpty()) {
		q.add(null);
		System.out.println();
		}
	} else {
		if (curr.left != null)
		q.add(curr.left);

		if (curr.right != null)
		q.add(curr.right);

		System.out.print(curr.data + " ");
	}
	}
}

public static void main(String[] args) {

	Node root = new Node(10);
	root.left = new Node(20);
	root.right = new Node(30);
	root.left.left = new Node(40);
	root.left.right = new Node(50);
	root.right.right = new Node(60);

	levelOrder(root);
}
}

So, in this blog, we have tried to discuss for a Given binary tree, print the nodes level by level or level wise and each level on a new line.. If you want to strengthen your basic data structures knowledge feel free to check Foundation Courses at Prepbytes.