Question

Write in C++

Build and run your project. The program should compile without any errors, but if does fix the errors . Note that function main() creates a new BST of int and inserts the nodes 12, 38, 25, 5, 15, 8, 55 (in that order) and displays them using pre-order traversal. Verify that the insertions are done correctly.

1. Add code to test the deleteNode and search member functions. Save screenshot of your test program run.

2. Add code to implement the nodeCount member function of class BinaryTree. Test it and save screenshot of your test program run.

3. Add code to implement the leafCount member function of class BinaryTree. Test it and save screenshot of your test program run.

4. The insert member function uses an iterative algorithm to insert a new value into the BST. Define a new insert function name it recursiveInsert that uses a recursive algorithm instead. Write a test program to test your function and save a screenshot of a test run showing your insert function works properly.

Answer 1

//C++ program

#include<iostream>
#include<stdlib.h>
using namespace std;

  

class BST{
private:
   struct node
   {
int key;
struct node *left, *right;
   };
  
   struct node*root;

   struct node* insert(struct node* Node , struct node*newNode)
   {
if (Node == NULL) return newNode;

if (newNode->key < Node->key)
Node->left = insert(Node->left, newNode);
else if (newNode->key > Node->key)
Node->right = insert(Node->right, newNode);   

return Node;
   }

   struct node*findmin(struct node*tree){
   while(tree->left){
       tree=tree->left;
   }
   return tree;
}

node*deletenode(struct node*tree, int key){
   node*temp;
   if(!tree)return NULL;
   else if(tree->key<key)tree->right=deletenode(tree->right,key);
   else if(tree->key>key)tree->left=deletenode(tree->left,key);
   else if(tree->key==key){
       if(!tree->left){
           temp=tree->right;
           delete(tree);
           return temp;
       }
       if(!tree->right){
           temp=tree->left;
           delete(tree);
           return temp;
       }
       temp=findmin(tree->right);
       tree->key=temp->key;
       deletenode(tree->right,temp->key);
   }
   else
       cout<<"key not found\n";
  
  
   return tree;
}

bool search(struct node* Node, int key)
{
if(Node == NULL)return false;
if (Node->key == key) return true;
  
if (Node->key < key)
return search(Node->right, key);
  
return search(Node->left, key);
}

int size(struct node*Node){
   if(!Node)return 0;
   return 1+size(Node->left)+size(Node->right);
}

void Recpreorder(struct node*Node ){
   if(!Node)return;
   cout<<Node->key<<" ";
   Recpreorder(Node->left );
   Recpreorder(Node->right);
}
int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;   
else
return getLeafCount(node->left)+ getLeafCount(node->right);
}

public:
   BST(){
   root=NULL;
}
  
void Insert(int item)
   {
struct node *temp = new struct node;
temp->key = item;
temp->left =NULL;
   temp->right = NULL;
root= insert(root,temp);
   }
  
   void Delete(int item){
       root= deletenode(root,item);
   }
  
   bool Search(int item){
       return search(root,item);
   }
   int nodeCount(){
       return size(root);
   }
   void preorder(){
       Recpreorder(root);
   }
   int leafCount(){
      return getLeafCount(root);
   }
  
};

int main(){
   BST bst;
   bst.Insert(12);
   bst.Insert(38);
   bst.Insert(25);
   bst.Insert(5);
   bst.Insert(15);
   bst.Insert(8);
   bst.Insert(55);
  
   cout<<"Preorder Traversal\n";
   bst.preorder();
   cout<<"\n\n";
   if(bst.Search(38))cout<<"found in binary search tree\n";
   else cout<<"Not found in binary search tree\n";
   cout<<"\nNumber of total nodes : "<<bst.nodeCount()<<"\n\n";
   cout<<"deleting 5 .........\n";
   bst.Delete(5);
   bst.preorder();
  
   cout<<"\nNumber of total nodes : "<<bst.nodeCount()<<"\n\n";
   cout<<"Number of leaf nodes : "<<bst.leafCount()<<"\n";
  
   return 0;
}
//sample output