delete node from binary search tree algorithm code example
Example: deletion in a binary search tree
#include <iostream>
using namespace std;
class node
{
public:
int data;
node*right;
node*left;
};
node*getnewnode(int val)
{
node *temp=new node;
temp->data=val;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int getrightmin(node*root)
{
node*temp=new node;
temp=root;
while(temp->left!=NULL)
{
temp=temp->left;
}
return temp->data;
}
node*insertbst(node*root,int val)
{
if(root==NULL)
{
return getnewnode(val);
}
if(root->data>val)
{
root->left= insertbst(root->left,val);
}
else
{
root->right= insertbst(root->right,val);
}
return root;
}
int searchbst(node*root,int val)
{
if(root==NULL)
{
return 0;
}
if(root->data==val)
{
return 1;
}
if(root->data<val)
{
return searchbst(root->right,val);
}
else
{
return searchbst(root->left,val);
}
}
node*removebst(node*root,int val)
{
if(root==NULL)
{
return 0;
}
if(root->data>val)
{
root->left=removebst(root->left,val);
}
else if(root->data<val)
{
root->right=removebst(root->right,val);
}
else
{
if(root->left==NULL&&root->right==NULL)
{
delete root;
return NULL;
}
else if(root->left==NULL)
{
node*temp=new node;
temp=root->right;
delete root;
return temp;
}
else if(root->right==NULL)
{
node*temp=new node;
temp=root->left;
delete root;
return temp;
}
else
{
int min=getrightmin(root->right);
root->data=min;
root->right=removebst(root->right,min);
}
}
return root;
}
void inorder(node*root)
{
if(root==NULL)
{
return;
}
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
int main()
{
node*root=new node;
root=NULL;
while(1)
{
int value;
cout<<"1.Insert to bst"<<endl<<"2.search in bst:"<<endl<<"3.display ordered bst"<<endl<<"4. exit"<<endl<<"5. delete "<<endl;
int n;
cout<<"enter your choice:"<<endl;
cin>>n;
switch(n)
{
case 1:
{
cout<<"enter the value to be inserted:"<<endl;
cin>>value;
root=insertbst(root,value);
break;
}
case 2:
{
cout<<"enter the value you want to search:"<<endl;
int search;
cin>>search;
int s=searchbst(root,search);
if(s==1)
{
cout<<"value found"<<endl;
}
else
{
cout<<"value not found:"<<endl;
}
break;
}
case 3:
{
inorder(root);
cout<<endl;
break;
}
case 4:
{
exit(0);
break;
}
case 5:
{
int val;
cout<<"enter the value to be deleted:"<<endl;
cin>>val;
removebst(root,val);
break;
}
default:
{
cout<<"invalid choice given:"<<endl;
break;
}
}
}
return 0;
}