DS – BST Node Deletion

Node deletion:

  • We need to find whether the element is present or not.
  • If the element is present, we need to delete the node and re-arrange other nodes.
  • If not present, display “Element not Found”.

Case 1: Deleting node with no child

Code to delete leaf node in BST:

if(curr->left==NULL && curr->right==NULL)
{
            if(curr==parent->right){
                        parent->right=NULL;
            }
            else{
                        parent->left=NULL;
            }
            printf(“Deleted \n”);
            free(curr);
}

Case 2: Deleting element that has single child

  • We need to consider the following 4 situations to delete the node with single child.
  • After deletion, we need to connect the node which is connected to the deleted node to parent.
if((curr->left != NULL && curr->right==NULL) || (curr->right != NULL && curr->left==NULL))
{
            if(curr->left != NULL && curr->right==NULL)
            {
                        if(curr == parent->right)
                        {
                                    parent->right = curr->left;
                        }
                        else
                        {
                                    parent->left = curr->left;
                        }
                        curr->left=NULL;
                        free(curr);        
            }          
            else
            {
                        if(curr == parent->right)
                        {
                                    parent->right = curr->right;
                        }
                        else
                        {
                                    parent->left = curr->right;
                        }
                        curr->right=NULL;
                        free(curr);
            }
}

Case 3: Deleting the node has 2 children.

  • Replace the current node data with
    • Least element in the right sub tree or
    • Highest element in the left sub tree.
  • Removes the data swapped node.

If the target node has any left or right child, that will be connected to its parent as follows:

Condition to confirm that the node has two children:

if(curr->left!=NULL && curr->right != NULL)
{
            Logic…
}

If curr-> right has no left child and right child:

t1 = curr->right ;
if(t1->left == NULL && t1->right == NULL)
{
            curr->data = t1->data;
            curr->right = t1->right;
            free(t1);
}

If curr-> right has no left child but right child is present:

if(t1->right!=NULL && t1->left==NULL)
{
            curr->data=t1->data;
            curr->right=t1->right;
            t1->right=NULL;
            free(t1);
}

If curr->right has left child:

  • We can find the least values on the left side of tree.
  • We need to move all the way down to find the least values in right sub tree.
  • Once we found, we replace the current node data with least node data and delete that node.
t1 = curr->right;
if(t1->left != NULL)
{
            t2 = t1->left;
}
while(t2->left)
{
            t1 = t1->left;
            t2 = t2->left;               
}
curr->data = t2->data;
t1->left = t2->right;
t2->right = NULL;
free(t2);
Copyright © 2023 Ameerpet Technologies | Powered by Ameerpet Technologies
Scroll to Top