Algorithm :-
To delete a node from a bst we have two measure cases :-1. If the node which we are deleting does not have either of left child or right child then its easier just point the parent to left or right of the node and delete the node.
2. When we have both the children of node then we need to find the immediate inorder succesor i.e. next element in the right tree which can be replaced with the node and that we can find out using the minimum element in the right tree of the node and delete the node again which we were going to recurse.
C++ Code
========
/* To find the minimul value of the given tree */int minval(btptr t)
{
btptr temp=t;
while(t!=NULL)
{
temp=t;
t=t->left;
}
return (temp->data);
}
/* Function to Delete the Data node from the BST */
btptr delete_bst(btptr t, int data)
{
if (t!= NULL)
{
if (data < t->data)
t->left=delete_bst(t->left,data);
else if (data>t->data)
t->right=delete_bst(t->right,data);
if (t->data==data)
{
/* Check whether left of right is null */
btptr temp=NULL;
if (t->left == NULL)
{ temp=t->right; t->right=NULL; return temp;}
if (t->right == NULL)
{ temp=t->left ; t->left=NULL; return temp;}
/* If both left and right children are not null */
int tdata =minval(t->right);
t->data=tdata;
t->right=delete_bst(t->right,tdata);
return t;
}
return t;
}
}
Additional code used.
typedef struct bnode
{
int data;
bnode *left;
bnode * right;
} *btptr;
btptr mknode(int data)
{
btptr temp= new (bnode);
temp->data=data;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void create(btptr &t, int data)
{
if (t == NULL)
t = mknode(data);
else
{
btptr p=t,q=t;
while (q!=NULL)
{
if (data < q->data) {
p=q;
q=q->left;}
else
{
p=q; q=q->right;
}
}
if (data > p->data)
p->right=mknode(data);
else
p->left=mknode(data);
}
}
int main()
{
btptr t=NULL;
create_tree(t,5);
create_tree(t,10);
create_tree(t,2);
create_tree(t,14);
create_tree(t,12);
create_tree(t,3);
create_tree(t,1);
create_tree(t,9);
create_tree(t,7);
}
