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
