Last Updated on March 29, 2022 by Ria Pathak
Concepts Used
BFS , Queue
Difficulty Level
Easy
Problem Statement :
Given a binary tree, our task is to print the level order traversal of the tree.
See original problem statement here
Solution Approach :
Introduction :
In level order traversal , each node is visited level-wise (level by level), starting from left to right. Simple solution is to print all the nodes at level 1, then level 2…..upto level
h, wherehis the height of the tree.
Approach :
We will use Queue to store the traversal, we need to traverse left to right (left node then right node), for each level.
We will create an empty queue
Q, push the root node intoQ, & perform the following steps whileQis not empty :
-
Extract the front node from
Qand store it in a temporary node pointer, i.e.temp = Q.front(), print its value, & remove the front node (Q.pop()). -
If
temp->left != NULL, then push the left node inQ. Do the same for right node.
Below is the implementation of this aproach.
Complexity Analysis :
We are traversing every node once so time complexity of this approach is
O(n).
SOLUTIONS:
#include <stdio.h>
#include<stdlib.h>
#define ll long long
#define REP(i, n) for (i = 0; i < n; i++)
struct nodelist
{
ll value;
struct nodelist *left;
struct nodelist *right;
};
typedef struct nodelist node;
struct Queue
{
int front, rear, size;
unsigned capacity;
node* *array;
};
typedef struct Queue queue;
queue* createQueue(unsigned capacity)
{
queue* qu =(queue*)malloc(sizeof(queue));
qu->capacity = capacity;
qu->front = qu->size =0;
qu->rear = capacity-1;
qu->array = (node **)malloc(qu->capacity * sizeof(node));
return qu;
}
int isFull(queue* queue1)
{
return (queue1->size == queue1->capacity);
}
int isEmpty(queue* queue1)
{
return (queue1->size==0);
}
void enqueue(queue* queue1, node* item)
{
if(isFull(queue1))
return ;
queue1->rear = (queue1->rear +1 )%queue1->capacity;
queue1->array[queue1->rear] = item;
queue1->size = queue1->size +1;
}
node dequeue(queue* queue1)
{
node* item = queue1->array[queue1->front];
queue1->front = (queue1->front +1)%queue1->capacity;
queue1->size = queue1->size -1;
return *item;
}
node* front(queue* queue1)
{
return queue1->array[queue1->front];
}
node* rear(queue * queue1)
{
return queue1->array[queue1->rear];
}
node *createNode(ll value)
{
node *t= (node *) malloc(sizeof(node));
t->value = value;
t->right = t->left = NULL;
return t;
}
void deleteNode(node*t)
{
free(t);
}
node *replaceNegativeOne(node *root)
{
if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}
void deleteTree(node *node1)
{
if(node1==NULL)
return;
deleteTree(node1->left);
deleteTree(node1->right);
free(node1);
}
node *createTreeByLevelTree()
{
ll n,m;
queue* queue1 = createQueue(100000);
node *root, *t;
root = NULL;
while(scanf("%lld", &n))
{
if(isEmpty(queue1))
{
root= createNode(n);
enqueue(queue1,root);
continue;
}
scanf("%lld", &m);
t = front(queue1);
dequeue(queue1);
t->left =createNode(n);
t->right=createNode(m);
if(t->left->value !=-1)
enqueue(queue1,t->left);
if(t->right->value !=-1)
enqueue(queue1,t->right);
if(isEmpty(queue1))
break;
}
return root;
}
void levelOrderTraversal(node *t)
{
queue* q = createQueue(1000);
enqueue(q,t);
while(!isEmpty(q))
{
node * temp = front(q);
printf("%d ", temp->value);
dequeue(q);
if(temp->left!= NULL)
enqueue(q,temp->left);
if(temp->right!= NULL)
enqueue(q,temp->right);
}
}
int main() {
node *root = NULL;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
levelOrderTraversal(root);
deleteTree(root);
return 0;
}
#define REP(i, n) for (i = 0; i < n; i++)
#define pb(a) push_back(a)
#define vi vector<long>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
struct node
{
ll value;
node *left;
node *right;
};
node *createNode(ll value)
{
node *t = new node();
t->value = value;
t->right = t->left = NULL;
return t;
}
void deleteNode(node *t)
{
delete t;
}
node *replaceNegativeOne(node *root)
{
if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}
node *createTreeByLevelTree()
{
ll n, m;
queue<node *> q;
node *root, *t;
root = NULL;
while (cin >> n)
{
if (q.empty())
{
root = createNode(n);
q.push(root);
continue;
}
cin >> m;
t = q.front();
q.pop();
t->left = createNode(n);
t->right = createNode(m);
if (t->left->value != -1)
{
q.push(t->left);
}
if (t->right->value != -1)
{
q.push(t->right);
}
}
return root;
}
void deleteTree(node *node)
{
if (node == NULL)
return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
void levelOrderTraversal(node *t)
{
queue<node*> q;
q.push(t);
while(!q.empty())
{
node* temp = q.front();
q.pop();
cout<<temp->value<<" ";
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
int main()
{
node *root = NULL;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
levelOrderTraversal(root);
//doYourThing(root);
deleteTree(root);
return 0;
}
import java.util.*;
import java.util.*;
import java.util.Scanner;
import java.io.*;
class Node
{
long value;
Node left, right;
public Node(long item)
{
value = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() {
root = null;
}
Node createNode(long value) {
Node t = new Node(value);
return t;
}
Node replaceNegativeOne(Node root) {
if (root == null || (root.value == -1 && root.left == null && root.right == null)) {
return null;
}
root.left = replaceNegativeOne(root.left);
root.right = replaceNegativeOne(root.right);
return root;
}
Node createTreeByLevelTree() {
Scanner sc = new Scanner(System.in);
long n, m;
Queue<Node> queue = new LinkedList<>();
Node t;
root = null;
while (sc.hasNext()) {
n = sc.nextLong();
if (queue.isEmpty()) {
root = createNode(n);
((LinkedList<Node>) queue).add(root);
continue;
}
m = sc.nextLong();
t = ((LinkedList<Node>) queue).peekFirst();
((LinkedList<Node>) queue).pop();
t.left = createNode(n);
t.right = createNode(m);
if (t.left.value != -1)
((LinkedList<Node>) queue).add(t.left);
if (t.right.value != -1)
((LinkedList<Node>) queue).add(t.right);
if (queue.isEmpty())
break;
}
return root;
}
void deleteTree(Node node) {
node = null;
}
void levelOrderTraversal(Node node) {
Queue<Node> q= new LinkedList<>();
q.add(node);
while(!q.isEmpty())
{
Node temp = q.remove();
System.out.print(temp.value+" ");
if(temp.left!=null)
q.add(temp.left);
if(temp.right!=null)
q.add(temp.right);
}
}
}
public class Main {
public static void main(String[] args) {
// write your code here
BinaryTree bt = new BinaryTree();
bt.root = bt.createTreeByLevelTree();
bt.root = bt.replaceNegativeOne(bt.root);
bt.levelOrderTraversal(bt.root);
bt.deleteTree(bt.root);
}
}
[forminator_quiz id="1712"]
This article tried to discuss BFS , Queue. Hope this blog helps you understand and solve the problem. To practice more problems on BFS , Queue you can check out MYCODE | Competitive Programming.