Question

I was trying to implement a simple binary search tree using this given class of bst in c++

public:
BST();
~BST();
void insertKey(int newKey);
bool hasKey(int searchKey);
std::vector<int> inOrder();
int getHeight();

however; i am still required to use another class for the nodes as a pointer and i need to manage memory leak.

in main we should ask for the numbers we need to insert in the binary search tree and also let the user end it with a letter to stop like "1 2 3 q"

Answer 1

Hey here is the update code along with image.I have writen comments in the code also

I have updated the get height functions.I have written the destructor function also and it will be called for all the nodes as we need to delete them all and change the status of root to NULL;

#include <iostream>
# include <bits/stdc++.h>
using namespace std;

//Node class for each individual pointer node in a BST
class Node{

 public:

  int val;
  Node* left;
  Node * right;
  //Consteructor for Node class
 Node(int val)
 {
     
    this->val=val;
    this->left=NULL;
    this->right=NULL;
     
 }
    
    
};
class BST{
   
   Node *root;
   
  public:
   
   BST(){
       
   }
   
   //Insert key function which  has a helper recursive function
   void insertKey(int newKey){
       
       
      root=insertRec(newKey,root);
       
   }
   //This is recursive implementation of insertKey  because it takes root as the parameter which keeps changeing
   Node* insertRec(int newKey,Node*root)
   {
        
       if(root==NULL)
       {
          Node * curr=new Node(newKey);
          return curr;
           
       }
       
       if(root->val<newKey)
       {
           root->right=insertRec(newKey,root->right);
       }
       else
        root->left=insertRec(newKey,root->left);
       return root;
       
   }
   
   //Check key function which has a heper recursive function
bool hasKey(int searchKey){
    
    
     return  recurhasKey(searchKey,root);
    
}

//This is recursive implementation of checkKey  because it takes root as the parameter which keeps changeing
bool recurhasKey(int searchKey,Node * root)
{
     
       if(root==NULL)
       {
         return false;;
           
       }
       
       if(root->val<searchKey)
       {
           return recurhasKey(searchKey,root->right);
       }
       else if(root->val==searchKey)
        return true;
        else
                   return recurhasKey(searchKey,root->left);

        
        
}
//Function for creating inordr epresentation in vector
std::vector<int> inOrder(){
    vector<int> v;
    //Passing vector as reference
     recurInorder(root,v); 
     return v;
    
}
//This is recursive implementation of inOrder  because it takes root as the parameter which keeps changeing nad vector is passed as reference
 void recurInorder(Node * root,vector<int> &v)
 {
     if(root==NULL)
       return;
     
       recurInorder(root->left,v);
        v.push_back(root->val);
       recurInorder(root->right,v);
 }
 
 //Function to get height of the tree which also has a helper
    int getHeight(){
        
        return recurgetHeight(root);
    }
    //This is recursive implementation of getHeight  because it takes root as the parameter which keeps changeing
 int recurgetHeight(Node * root)
  {
      if(root==NULL)
       return 0;
       
       return 1+max(recurgetHeight(root->left),recurgetHeight(root->right));
      
  }
  //Overidding destructor for BST call and we need helper recursive function as we need to delete all the nodes recursively using delete keyword
 ~BST(){
     cout<<"Destructor called"<<endl;
      recurDelete(root);
     root=NULL;
     
 }
 private:
    void recurDelete(Node *root){
        
        if(root==NULL)
          return ;
          recurDelete(root->left);
          recurDelete(root->right);
          delete(root);
          root=NULL;
          cout<<"Node deleted"<<endl;
    }
    
    
};


 bool isInteger(string str)
{
    for(int i=0;i<str.size();i++)
    {
         if(!isdigit(str[i]))
         return false;
    }
    return true;
    
}


int main()
{
    BST *tree=new BST();

    string str;
//Taking user input till the user inputs a q or Q
 while(cin>>str)
 {
     
     //Calling helper function to check if input is integer or not
     if(!isInteger(str))
      break;
     
     int v=stoi(str);
     
      tree->insertKey(v);
 }

   
    // tree->insertKey(v);
    vector<int> v= tree->inOrder();
    //Printing vector
     for(int i=0;i<v.size();i++)
       cout<<v[i]<<" ";
      cout<<endl;
     cout<<"The height of tree is : "<<tree->getHeight();  
   delete(tree);
   
   return 0;
}