Data Structures and Algorithms - Old Questions

12. Write the steps involved in deleting a node in a Binary search tree.

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