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
  CS604 Assignment 3 Solution Pakistani 2 149 07-26-2017, 06:17 PM
Last Post: Rubaisha(Moody Girl)
  CS615 Assignement 3rd solution 2017 Rubaisha(Moody Girl) 0 105 07-26-2017, 12:13 PM
Last Post: Rubaisha(Moody Girl)
  CS507 Assignment solution Rubaisha(Moody Girl) 0 89 07-25-2017, 10:23 PM
Last Post: Rubaisha(Moody Girl)
  CS601 Assignment 4 Solution Rana 0 376 07-24-2017, 11:49 AM
Last Post: Rana
  CS401 Assignment 3 Solution Pakistani 0 219 07-21-2017, 01:34 PM
Last Post: Pakistani
  CS504 Assignment 3 Rana 7 810 07-19-2017, 08:06 AM
Last Post: Rana
  CS502 Assignment 3 Solution Pakistani 0 226 07-18-2017, 10:00 AM
Last Post: Pakistani
  CS201 GDB Solution 2017 Rubaisha(Moody Girl) 0 207 07-14-2017, 06:44 PM
Last Post: Rubaisha(Moody Girl)
  CS605 assignment-3 Solution Nadeem Rana vu 1 115 07-14-2017, 05:49 PM
Last Post: Pakistani
  CS601 Assignment 3 Solution Pakistani 2 316 07-13-2017, 10:57 AM
Last Post: Rana



Users browsing this thread:
1 Guest(s)