CS301 Assignment 2 Solution and Discussion Spring 2020

zaasmi

Re: CS301 Assignment 2 Solution and Discussion

Assignment No. 02

Spring 2020
CS301- Data Structures
Total Marks: 20

Due Date: 17-Jun-2020
Instructions
Please read the following instructions carefully before solving & submitting assignment:
It should be clear that your assignment will not get any credit (zero marks) if:
 The assignment is submitted after due date.
 The submitted assignment is other than .CPP file.
 The submitted code does NOT compile.
 The submitted assignment does NOT open or file is corrupted.
 The assignment is copied (from other student or ditto copy from handouts or internet).

Uploading instructions
For clarity and simplicity, you are required to upload/submit only one .CPP file.

Note: Use only Dev-C++ IDE.

Objectives
The objectives of this assignment are;

 To make you familiar of programming with Tree data structure
 To traverse Binary Search Tree (BST) using different techniques
 To perform some basic operations on BST

For any query about the assignment, contact at [email protected]

Good Luck!

Total Marks: 20

Problem Statement:

As you know, Binary Search Tree (BST) has property that on the addition of a node in the tree, we compare it with root node. If new node is less than root node, it can be added to the left sub-tree. Otherwise, it will be added to the right sub-tree. So, the BST will have numbers (or nodes) less than the root in the left sub-tree and the numbers greater than the root will be in the right sub-tree.

Following is a snapshot of Binary Search Tree (BST).

You are required to develop a C++ program implementing Binary Search Tree (BST) data structure for the above scenario.

For this you need to;

Construct Binary Search Tree, based upon above given tree data
Calculate minimum node (or number), maximum node, height and total number of nodes for BST
Details:

Your solution must contain a tree node class named as TNode, insert() method, buildTree() method, minNode() method, maxNode() method, treeHeight() method and countNodes() method. You should call BuildTree() method in main() method and call insert() method inside BuildTree() method so that insert() method can actually add nodes in BST.

You must call the above-mentioned methods from main to calculate minimum node, maximum node, height and total number of nodes for the BST.

Remember, the height of root node is 1 while depth or level of root node is 0 in tree.

Required Output:

Note:
Make sure to follow class name, method names and variable/objects names as mentioned above in the scenario. Moreover, your solution must be according to the Required Output. Otherwise, you will get Zero marks.
Lectures Covered: Lecture No. 09 to 16.
Deadline: Your assignment must be uploaded / submitted on or before, Jun 17, 2020.

zareen

#include<iostream>

using namespace std;
	
		class TNode{
			
			private:
					node* root;
			public:				
					TNode();
					int isEmpty();
					void buildTree(int item);
					void insert(int item,node *,node *);						
					void minNode(node*);
					void maxNode(node*); 
					int countNodes(node*);
					int treeHeight(node*);
					void displayBinTree();
		};
		
		TNode::TNode(){
			
				root = NULL;
			}
			
		int TNode::isEmpty() {
					
				return (root == NULL);
			}
		
		void TNode::buildTree(int item){
		
			node *p = new node;
			node *parent;
			
			cout <<"Insert node in BST :" << item <<endl;
			insert(item,p,parent);
		}	
	
		void TNode::insert(int item,node * p,node * parent){
	
				p->data=item;
				p->left=NULL;
				p->right=NULL;
				parent=NULL;
				
				if(isEmpty()){
					root = p;
				}					
				else{
					
					node *ptr;
					ptr = root;
					
					while(ptr != NULL){
						parent = ptr;
						if(item > ptr->data){
							ptr = ptr->right;	
						}							
						else{
							ptr = ptr->left;
						}
							
					}	
					if(item < parent->data){
						parent->left = p;
					}						
					else{
						parent->right = p;	
					}
						
				}
	}		
		
	void TNode::minNode(node* p){   

	    while (p->left != NULL){
	
	        p = p->left;
	    }
		cout << "Minimum value : " << p->data <<endl;
	}
	
	void TNode::maxNode(node* p){   

	    while (p->right != NULL){
	
	        p = p->right;
	    }
		cout << "Maximum value : " << p->data <<endl;
	}
	
	int TNode::countNodes(node* p){
		
		int node =  1;             //Node itself should be counted
	    if (p == NULL){
	    	
	    	return 0;
		}        
	    else{
	    	
	        node += countNodes(p->left);
	        node += countNodes(p->right);
	        return node;
	    }
	}
	
	int TNode::treeHeight(node* p){		
		
	    if (p == NULL) 
		{
			return 0;	
		} 	          
	    else
	    {  
	        
	        int left_side = treeHeight(p->left);  
	        int right_side = treeHeight(p->right);  
	      
	        
	        if (left_side > right_side)
			{
				return(left_side + 1);	
			} 	              
	        else 
			{
				return(right_side + 1); 	
			} 
	    }  
	    
	}
	
	void TNode::displayBinTree(){
		cout <<endl<<endl;		
		minNode(root);
		maxNode(root);
		cout <<"Height of BST : "<<treeHeight(root);
		cout <<"\nTotal nodes : "<<countNodes(root);
		
	}

	int main(){
		
		TNode b;
	
		int data[] = {7,2,9,1,5,14};
		
		cout <<"Constructing Binary Search Tree by Inserting Nodes One by One "<<endl;
		cout <<"------------------------------------------------------------- "<<endl;
		int arrSize = sizeof(data)/sizeof(data[0]);
		
		for(int i = 0; i < arrSize; i++)
		{
			b.buildTree(data[i]);
		}
	}