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.

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 by referring some online programming courses, 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;

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

    }

}

Previous post Ancestors
Next post Maximum Turns

Leave a Reply

Your email address will not be published. Required fields are marked *