150 views

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.

Tags: CS201 Assignment No.2 Solution
CS201 Assignment No.2 Solution 2020
CS201 Assignment No.2 Solution Spring 2020
CS201 Assignment 2 Solution
CS201 Assignment 2 Solution 2020
CS201 Assignment 2 Solution Spring 2020
CS201 Assignment 2 2020 Solution
CS201 Assignment 2 Spring 2020 Solution
CS201 Assignment 2 2020
CS201 Assignment No 2 Solution
CS201 Assignment No 2 Solution 2020
CS201 Assignment No 2 Solution Spring 2020
CS201 Assignment No 2 2020 Solution
CS201 Assignment No 2 Spring 2020 Solution
CS201 Assignment No 2 2020

| 150 views

+1 vote

Here is the solution:

``````#include<iostream>
using namespace std;
struct node{
node *left;
node *right;
int data;
};
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]);
}

b.displayBinTree();
}
``````
by (3.3k points)