cs301 assignment no 2 2020

Question

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

Answer 1

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();
}