Deletion in a Binary Tree

In the previous article, we learned about the Insertion operation in a Binary Tree in Data Structures, In this article, we will learn about the Deletion operation in Binary Tree in Data Structures.

231

Deletion in a binary tree operation means deleting a specific node from the tree. The deletion operation is a bit more complex than the insertion in a binary tree as it involves a variety of cases such as

  • Case 1 – The node to be deleted is a leaf node.
  • Case 2 – The node to be deleted has one child.
  • Case 3 – The node to be deleted has two children

Also check: spanning tree in data structure

The node to be deleted is a leaf node

If the node to be deleted is a root node, assign NULL to the root. If the node to be deleted is the left child of its parent, assign NULL to the left address part of its parent. If the node to be deleted is the right child of its parent, assign NULL to the right address part of its parent.

void del_cas1(struct node* par, struct node* loc){

if(par == NULL){

root = NULL;

                     else if(loc == par->child)

                                       par->lchild = NULL;

                     else if(loc == par->rchild)

                                       par->rchild = NULL;

}

The node to be deleted has one child

If the node to be deleted has either a left or right child then it can be deleted by storing the address of its child in the address part of its parent. First, check whether the node to be deleted has the left child or the right child. If it has the left child, store its address in some pointer variable, say, child. Similarly, if it has the right child, store its address in the pointer variable child.

Also check: Bellman ford algorithm in data structure

Now, check if the node to be deleted is the left child or the right child of its parent. If it is the left child, assign the value of the pointer variable child to the left address part of its parent; otherwise, assign the value of the pointer variable to the right part of its parent.

void del_case2(struct node* par, struct node* loc){

struct node* lchild;

if(loc->lchild !=NULL)

child = loc->lchild;

else

child = loc->rchild;

if(par == NULL)

root = child;

else if(loc == par->lchild)

par->lchild = child;

else      par->rchild = child;

}

Definition of del_case3():

The node to be deleted has two children

If the node to be deleted has both the children, then the first step is to find its inorder successor. In the next step, delete the inorder successor from the tree. To delete that, either del_case1() or del_case2() can be followed.

Also check: max heap deletion algorithm

Finally, the node to be deleted is replaced with the inorder successor. If the node to be deleted is the left child of the parent, assign the address of its successor in the left address part if the parent, otherwise, assigns the address of its successor in the right address part of its parent.

void del_case3(struct node* par, struct node* loc){

struct node* ptr,*parptr,*succ,*parsucc;

parptr = loc;

ptr =  loc->rchild;

while(ptr->rchild!=NULL){

    parptr = ptr;

    ptr = ptr->lchild;

    }

succ = ptr;

parsucc = parptr;

if(succ->lchild =  NULL && succ->rchild == NULL){

del_case1(parsucc,succ);

}

else

del_case2(parsucc,succ);

if(par == NULL)

    root = succ;

else if (loc == par->lchild)

    par->lchild = succ;

else if(loc == par->rchild)

    par->rchild = succ;

succ->lchild = loc->lchild;

succ->rchild = loc->rchild;

}

So, in this tutorial, we learned about the various cases that arise while deleting a specific element from a binary search tree.

Attempt free Data Structure MCQ Test

Previous QuizInsertion Operation in a Binary Tree
Next QuizWhat is an AVL Tree in Data Structures

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.