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
  Assignment Solutions Iram shahzad 2 137 05-22-2017, 08:21 AM
Last Post: Rana
  cs504 assignment 1 help needed Syed Muhammad Taha 3 222 05-10-2017, 04:44 PM
Last Post: Rana
  CS403 Assignment 1 help required Syed Muhammad Taha 3 220 05-06-2017, 06:50 PM
Last Post: Rana
  CS506 Assignment No1 Solved 2017 Rubaisha(Moody Girl) 0 311 05-05-2017, 02:11 PM
Last Post: Rubaisha(Moody Girl)
Thumbs Up cs402 Assignment jamshed Ansari 1 200 05-03-2017, 06:05 PM
Last Post: Rana
  CS610 Assignment 1 Pakistani 3 488 05-03-2017, 01:50 PM
Last Post: jamshed Ansari
  CS304 Assignement 1 full Solution 2017 Rubaisha(Moody Girl) 0 163 04-28-2017, 09:34 PM
Last Post: Rubaisha(Moody Girl)
  CS502 GDB Solution 2017 Pakistani 0 373 02-16-2017, 09:41 AM
Last Post: Pakistani
  CS601 Data Communication Assignment Solution Rana 2 1,339 02-07-2017, 06:00 PM
Last Post: Pakistani
  CS301 Assignment 3 Solution Rana 8 1,521 01-21-2017, 02:25 PM
Last Post: Rana



Users browsing this thread:
1 Guest(s)