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 Pakistani 2 1,248 07-09-2017, 07:13 PM
Last Post: Admin
  CS301 Assignment 3 Solution Admin 8 2,168 01-21-2017, 02:25 PM
Last Post: Admin
  CS301 Current Mid-Term Exam Admin 0 610 12-17-2016, 10:13 AM
Last Post: Admin
  CS301 All Current Final Term Papers 20 August 2016 to 02 September 2016 Rubaisha(Moody Girl) 0 577 08-20-2016, 01:06 PM
Last Post: Rubaisha(Moody Girl)
  CS301 GDB solution Rubaisha(Moody Girl) 0 781 08-09-2016, 09:38 AM
Last Post: Rubaisha(Moody Girl)
  cs301 current paper Nadeem Rana vu 0 646 05-29-2016, 03:42 PM
Last Post: Nadeem Rana vu
  CS301 Midterm solved papers Nadeem Rana vu 0 642 05-12-2016, 02:19 AM
Last Post: Nadeem Rana vu
  CS301 Past Papers by Moaaz Nadeem Rana vu 0 462 05-12-2016, 02:17 AM
Last Post: Nadeem Rana vu
  CS301 Solved Midterm Past Papers Nadeem Rana vu 0 516 05-12-2016, 02:16 AM
Last Post: Nadeem Rana vu
  CS301 Midterm solved papers Nadeem Rana vu 0 952 05-12-2016, 02:11 AM
Last Post: Nadeem Rana vu



Users browsing this thread:
1 Guest(s)