Trees Interview Questions | Levelorder Traversal

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.

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 :

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()).
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;

        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 .

LevelOrder Traversal

Concepts Used

Difficulty Level

Problem Statement :

Solution Approach :

Introduction :

Approach :

Complexity Analysis :

SOLUTIONS:

Leave a Reply Cancel reply

What is Computer Software? Types, System Software & Application Software

Spiral Model in Software Engineering: Phases, Advantages & Examples

Java Design Patterns: Types, Examples & Best Practices

What is DNS in Computer Networks: Types and Applications Explained

Primary Key vs Foreign Key: Database Fundamentals Explained

Combinational vs Sequential Circuits: Key Differences & Applications

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Concepts Used

Difficulty Level

Problem Statement :

Solution Approach :

Introduction :

Approach :

Complexity Analysis :

SOLUTIONS:

Leave a Reply Cancel reply