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
  need GDB CS301 solution raja kamran 3 813 08-10-2018, 10:35 AM
Last Post: Pakistani
  CS301 Assignment 3 Solution Spring 2018 Admin 6 2,009 07-27-2018, 09:49 AM
Last Post: Pakistani
Thumbs Up required CS301 solution fahadmukhtar 3 1,129 07-25-2018, 01:49 PM
Last Post: Admin
  CS301 Assignment 2 Solution Spring 2018 Admin 1 1,826 05-28-2018, 10:10 PM
Last Post: rabia nawaz
  cs 301 assignment 2 solution needed rabia nawaz 0 249 05-26-2018, 10:18 PM
Last Post: rabia nawaz
  Required CS301 - Data Structures assignment solution please Javed Latif 0 1,032 05-08-2018, 12:47 PM
Last Post: Javed Latif
  CS301 Assignment 3 Solution Pakistani 2 4,227 07-09-2017, 07:13 PM
Last Post: Admin
  CS301 Assignment 3 Solution Admin 8 4,305 01-21-2017, 02:25 PM
Last Post: Admin
  CS301 GDB solution Rubaisha(Moody Girl) 0 1,489 08-09-2016, 09:38 AM
Last Post: Rubaisha(Moody Girl)
  CS301 assignment1 text solution Nadeem Rana vu 1 1,289 05-07-2016, 06:00 PM
Last Post: Rubaisha(Moody Girl)



Users browsing this thread:
1 Guest(s)