Concepts Used

Queue, Basic Implementation

Difficulty Level

Easy

Problem Statement :

You are given a binary tree, you need to print the average of each level of the tree.

See original problem statement here

Solution Approach :

Introduction :

Suppose, we are at Level L. The number of nodes at this level is N and the sum of all nodes at this level is S.

Average of Level L= S/N

Description :

We will perform level order traversal using queues by referring the top online programming courses.
We can use 2 Queues, let’s say q1 & q2, one for performing level order traversal and another to sum all values of nodes and count the number of nodes at each level.

We will push the root node into q1, then perform the following operations while q1 is not empty:

  • While q1 is not empty , we will pop the node after adding the values of the nodes and counting the number of nodes present & then push it’s left & right node in the other queue q2.
  • When q1 has no values left, it will come out of the loop and we will calculate & print our average value for the current level.
  • Now, we will repeat the same process for q2 as well, by assigning the values of q2 to q1 and then removing all elements of q2 to store the new nodes.

Complexity Analysis :

We are visiting all the nodes once for level order traversal. What could be the time complexity of the above approach?
Since we are visiting all the nodes n, the time complexity of the above approach is linear i.e 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 findAverageLevel(node* root)

{


    queue* q = createQueue(40);


    enqueue(q,root);


 while(!isEmpty(q))
 {
  float nodes=0,sum=0,ans=0;
  queue* t = createQueue(40);

   while(!isEmpty(q))
   {

    node *temp = front(q);
    dequeue(q);
    sum += temp->value;
     nodes++;

    if(temp->left!=NULL)
     enqueue(t,temp->left);

    if(temp->right!=NULL)
     enqueue(t,temp->right);

    }

    q = t;
    ans = sum/nodes;
    printf("%.2f ", ans);


  }
  //cout<<ans*1.00;
}

int main() {



    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

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

        }

         if (q.empty())

        {

            break;

        }

    }



    return root;

}



void deleteTree(node *node)

{

    if (node == NULL)

        return;



    deleteTree(node->left);

    deleteTree(node->right);

    delete node;

}



void findAverageLevel(node* root)

{
  queue<node *> q,t;
  q.push(root);

 while(!q.empty())
 {
  float nodes=0,sum=0,ans=0;

   while(!q.empty())
   {

    node *temp = q.front();
    q.pop();
    sum += temp->value;
     nodes++;

    if(temp->left!=NULL)
     t.push(temp->left);

    if(temp->right!=NULL)
     t.push(temp->right);

    }

    q = t;
    ans = sum/nodes;
   printf("%.2f ", ans);
    while(!t.empty())
     t.pop();
  }
  //cout<<ans*1.00;
}

int main()

{

    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    findAverageLevel(root);

    deleteTree(root);

    return 0;

}

import java.util.LinkedList;

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 findAverageLevel(Node node) {

    //write your code here

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

        q.add(node);

        while(!q.isEmpty())

        {

           float sum=0,count=0;

            LinkedList<Node> t = new LinkedList<>();

            while(!q.isEmpty())

            {

                Node temp = q.getFirst();

                q.removeFirst();

                sum+=temp.value;

                count++;

                if(temp.left!=null)

                    t.add(temp.left);

                if(temp.right!=null)

                    t.add(temp.right);

            }

            q=t;

            System.out.printf("%.2f ",(sum/ count) );

        }

}




}

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

            bt.deleteTree(bt.root);

    }

}
Previous post Largest number smaller than or equal to N and digits in non-decreasing order
Next post Light in night

Leave a Reply

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