CS301 Assignment 2 Solution - Spring 2017
#1
CS301 - Data Structures
Assignment No. 02 - Semester: Spring 2017


Question Statement:

Create a Complete Binary Tree using Array which can add node/elements according to user input. After creating a Complete Binary Tree, you need to print all nodes of complete binary tree, calculate height of binary tree, range of levels, maximum possible leaf nodes, interior nodes in complete binary tree and find the maximum value in the given complete binary tree. 

Note: You must use only Array as data structure for implementation. 


Solution:

Code:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <conio.h>

using namespace std;

#define SIZE 50

struct node
{
   int data;
   struct node *right,*left;
};

struct node* newNode(int data)
{
   struct node* temp = (struct node*) malloc(sizeof( struct node ));
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}

struct Queue
{
   int front, rear;
   int size;
   struct node* *array;
};

struct Queue* createQueue(int size)
{
   struct Queue* queue = (struct Queue*) malloc(sizeof( struct Queue ));

   queue->front = queue->rear = -1;
   queue->size = size;

   queue->array = (struct node**) malloc(queue->size * sizeof( struct node* ));

   int i;
   for (i = 0; i < size; ++i)
       queue->array[i] = NULL;

   return queue;
}

int isEmpty(struct Queue* queue)
{
   return queue->front == -1;
}

int isFull(struct Queue* queue)
{  return queue->rear == queue->size - 1; }

int hasOnlyOneItem(struct Queue* queue)
{  return queue->front == queue->rear;  }

void Enqueue(struct node *root, struct Queue* queue)
{
   if (isFull(queue))
       return;

   queue->array[++queue->rear] = root;

   if (isEmpty(queue))
       ++queue->front;
}

struct node* Dequeue(struct Queue* queue)
{
   if (isEmpty(queue))
       return NULL;

   struct node* temp = queue->array[queue->front];

   if (hasOnlyOneItem(queue))
       queue->front = queue->rear = -1;
   else
       ++queue->front;

   return temp;
}

struct node* getFront(struct Queue* queue)
{  return queue->array[queue->front]; }

int hasBothChild(struct node* temp)
{
   return temp && temp->left && temp->right;
}

void insert(struct node **root, int data, struct Queue* queue)
{
   struct node *temp = newNode(data);
   if (!*root)
       *root = temp;

   else
   {
       struct node* front = getFront(queue);

       if (!front->left)
           front->left = temp;
           
       else if (!front->right)
           front->right = temp;

       if (hasBothChild(front))
           Dequeue(queue);
   }

   Enqueue(temp, queue);
}

int levelOrder(struct node* root)
{
    int count = 0;
    
   struct Queue* queue = createQueue(SIZE);

   Enqueue(root, queue);

   while (!isEmpty(queue))
   {
       struct node* temp = Dequeue(queue);

       count += 1;
       cout<<temp->data<<" ";

       if (temp->left)
           Enqueue(temp->left, queue);

       if (temp->right)
           Enqueue(temp->right, queue);
   }
   
   cout<<endl;
   return count;
}


int MaxValue(struct node* root)
{
    int maxValue = -1;
    
   struct Queue* queue = createQueue(SIZE);

   Enqueue(root, queue);

   while (!isEmpty(queue))
   {
       struct node* temp = Dequeue(queue);

       if(maxValue == -1)
        {
            maxValue = temp->data;
        }
        else if(maxValue < temp->data)
        {
            maxValue = temp->data;
        }

       if (temp->left)
           Enqueue(temp->left, queue);

       if (temp->right)
           Enqueue(temp->right, queue);
   }
   
   return maxValue;
}


int leafNodes(struct node* root)
{
    int TotalLeafNodes = 0;
    
   struct Queue* queue = createQueue(SIZE);

   Enqueue(root, queue);

   while (!isEmpty(queue))
   {
       struct node* temp = Dequeue(queue);
        
        if(temp->left == 0 && temp->right == 0)
        {
            TotalLeafNodes++;
        }
        
       if (temp->left)
           Enqueue(temp->left, queue);

       if (temp->right)
           Enqueue(temp->right, queue);
   }
   
   return TotalLeafNodes;
}


int InteriorNodes(struct node* root)
{
    int TotalInteriorNodes = 0;
    
   struct Queue* queue = createQueue(SIZE);

   Enqueue(root, queue);

   while (!isEmpty(queue))
   {
       struct node* temp = Dequeue(queue);
        
        if(temp->left != 0 && temp->right != 0)
        {
            TotalInteriorNodes++;
        }
        
       if (temp->left)
           Enqueue(temp->left, queue);

       if (temp->right)
           Enqueue(temp->right, queue);
   }
   
   return TotalInteriorNodes;
}


int main()
{
   struct node* root = NULL;
   struct Queue* queue = createQueue(SIZE);

    int value = 0;
    int countNodes = 0;
    int height = -1;
    int level = -1;
    int TotalNodes = 0;

    
    cout<<"Enter -1 to stop. Maximum input limit is " << SIZE <<endl<<endl;
    
   for(int i = 0; i<SIZE && value != -1; ++i)
   {
       cout << "Enter node value : ";
        cin >> value;
        
       if(value != -1)
       {
            insert(&root, value, queue);
        }
    }
    
    countNodes = levelOrder(root);
    
    if (countNodes == 1)
    {
        cout<< "\nMust have more than 1 node \n";        
    }
    else
    {
        height = log2(countNodes);
        level = height + 1;
        
        cout<<endl<<"\t\tTotal no of Nodes......................... : "<<countNodes;
       cout<<endl<<"\t\tHeight of tree ............................: "<<height;
       cout<<endl<<"\t\tLevel of tree ............................ : "<<level;
       cout<<endl<<"\t\tRange of levels........................... : 0-"<<height;
       cout<<endl<<"\t\tMaximum possible Leaf Nodes............... : "<<leafNodes(root);
       cout<<endl<<"\t\tInterior Nodes in complete Binary tree ... : "<<InteriorNodes(root);
       cout<<endl<<endl<<"\t\tMaximum value is ......................... : "<<MaxValue(root);
   
    }

   return 0;
}


NOTE: Do Not Copy/Paste - Understand the solution and write it yourself. Your laziness can get everyone a ZERO. Be Better!  
  


Possibly Related Threads…
Thread Author Replies Views Last Post
  CS301 Assignment 3 Solution Fall 2020 Ayra Suleman 0 1,343 01-25-2020, 11:33 PM
Last Post: Ayra Suleman
  CS301 3rd Assignment solution RashidRoger 0 1,317 01-20-2020, 10:21 AM
Last Post: RashidRoger
  CS301 GDB Solution Spring 2019 Ayra Suleman 0 2,129 08-01-2019, 10:24 PM
Last Post: Ayra Suleman
  CS301 Assignment 3 Solution Spring 2019 Ayra Suleman 0 2,619 07-26-2019, 06:59 PM
Last Post: Ayra Suleman
  CS311 Assignment 2 Solution Spring 2019 Mishi Khan 0 763 06-01-2019, 01:11 AM
Last Post: Mishi Khan
  CS301 Assignment 2 Solution Spring 2019 Mishi Khan 0 756 05-28-2019, 01:57 AM
Last Post: Mishi Khan
  cs301 Assignment 2 solution Muhammad Yaseen 0 482 05-24-2019, 04:03 PM
Last Post: Muhammad Yaseen
  CS301 Assignment Solution Spring 2019 Mishi Khan 0 590 05-11-2019, 09:36 PM
Last Post: Mishi Khan
  cs301 Assignment Muhammad Yaseen 0 439 05-11-2019, 04:45 PM
Last Post: Muhammad Yaseen
  CS301 GDB Solution Mishi Khan 0 967 02-08-2019, 01:42 AM
Last Post: Mishi Khan



Users browsing this thread:
1 Guest(s)