Data Structures and Algorithms - Old Questions
12. Write the steps involved in deleting a node in a Binary search tree.
Answer
AI is thinking...
Algorithm to delete the node in BST
struct bnode *delete(struct bnode *root, int item)
{
struct bnode *temp;
if(root==NULL)
{
printf(“Empty tree”);
return;
}
else if(item<root->info)
root->left=delete(root->left, item);
else if(item>root->info)
root->right=delete(root->right, item);
else if(root->left!=NULL &&root->right!=NULL) //node has two child
{
temp=find_min(root->right);
root->info=temp->info;
root->right=delete(root->right, root->info);
}
else
{
temp=root;
if(root->left==NULL)
root=root->right;
else if(root->right==NULL)
root=root->left;
free(temp);
}
return(temp);
}
Finding minimum element function:
struct bnode *find_min(struct bnode *root)
{
if(root==NULL)
return0;
else if(root->left==NULL)
return root;
else
return(find_min(root->left));
}
E.g.
1. Deleting leaf Node
2. Deleting node with right child
3. Deleting node with left child
4. Deleting a node having both right and left child
