Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# LevelOrder Traversal

Last Updated on March 29, 2022 by Ria Pathak

BFS , Queue

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`, where `h` is 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 into `Q`, & perform the following steps while `Q` is not empty :

1. Extract the front node from `Q` and store it in a temporary node pointer, i.e. `temp = Q.front()`, print its value, & remove the front node ( `Q.pop()`).

2. If `temp->left != NULL`, then push the left node in `Q`. 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;

Node t;

root = null;

while (sc.hasNext()) {

n = sc.nextLong();

if (queue.isEmpty()) {

root = createNode(n);

continue;

}

m = sc.nextLong();

t.left = createNode(n);

t.right = createNode(m);

if (t.left.value != -1)

if (t.right.value != -1)

if (queue.isEmpty())

break;

}

return root;

}

void deleteTree(Node node) {

node = null;

}

void levelOrderTraversal(Node node) {

while(!q.isEmpty())

{

Node temp = q.remove();

System.out.print(temp.value+" ");

if(temp.left!=null)

if(temp.right!=null)

}

}

}

public class Main {

public static void main(String[] args) {

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.