Please write in C++

******This, down below, is my Binary Search Tree Class that needs to be modified.

#include

#include

using namespace std;

class BST{

private:

struct node

{

string 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 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, string key){

node*temp;

if(!tree)return NULL;

else if(tree->keyright=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

return tree;

}

struct node* search(struct node* Node, string key)

{

if (Node == NULL || Node->key == key)

return Node;

if (Node->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 inorder(struct node*Node , string &arr){

if(!Node)return;

inorder(Node->left , arr );

arr+=Node->key+" ";

inorder(Node->right , arr );

}

void DecOrder(struct node*Node , string &arr){

if(!Node)return;

DecOrder(Node->right , arr );

arr+=Node->key+" ";

DecOrder(Node->left , arr );

}

public:

BST(){

root=NULL;

}

void Insert(string item)

{

struct node *temp = new struct node;

temp->key = item;

temp->left =NULL;

temp->right = NULL;

root= insert(root,temp);

}

void Delete(string item){

root= deletenode(root,item);

}

struct node*Search(string item){

return search(root,item);

}

int Size(){

return size(root);

}

string GetAllAscending (){

string arr="";

inorder(root,arr);

return arr;

}

string GetAllDescending (){

string arr="";

DecOrder(root,arr);

return arr;

}

};

int main()

{

BST bst1;

string arr1[] = {"Star Wars", "Star Trek", "Space Balls", "Galaxy Quest"};

for(int i=0;i

bst1.Insert(arr1[i]);

}

cout

cout

cout

BST bst2;

string arr2[] = {"Cars", "Monsters" , "Inc", "The Incredibles", "Wall-E"};

for(int i=0;i

bst2.Insert(arr2[i]);

}

cout

cout

cout

BST bst3;

string arr3[] = {"Halloween", "A Nightmare On Elm Street", "Hocus Pocus", "Beetlejuice"};

for(int i=0;i

bst3.Insert(arr3[i]);

}

cout

cout

cout

return 0;

}

Objective The objective of this Lab is to create an implementation of a Binary Search Tree that remains in constant balance. Requirements: 1. Modifv youu Binary.Search Tree class.from Lab.6 to xemain balanced at alltimes Create a menu that allows the user to: Add items to the tree. Remove items from the tree a. b. 2. Create a print function that displays the contents of the tree. Irecommend you do this horizontally rather than vertically (as demonstrated below) Tree represented by the output on the left -4 4 2 1 Objective The objective of this Lab is to create an implementation of a Binary Search Tree that remains in constant balance. Requirements: 1. Modifv youu Binary.Search Tree class.from Lab.6 to xemain balanced at alltimes Create a menu that allows the user to: Add items to the tree. Remove items from the tree a. b. 2. Create a print function that displays the contents of the tree. Irecommend you do this horizontally rather than vertically (as demonstrated below) Tree represented by the output on the left -4 4 2 1