Binary Tree – Deleting a Node

The possibilities which may arise during deleting a node from a binary tree are as follows:

  • Node is a terminal node: In this case, if the node is a left child of its parent, then the left pointer of its parent is set to NULL. Otherwise if the node is a right child of its parent, then the right pointer of its parent is set to NULL
  • Node has only one child: In this case, the appropriate pointer of its parent is set to child node.
  • Node has two children: Predecessor replaces the node value, and then the predecessor of the node is deleted.

Since the node has both, right and left child, if right sub-tree is opted find the smallest node. If left sub-tree is opted then find the largest node.

Since node->right = node->left = NULL, delete the node and place NULL in the parent node.

Node Removal Operation

If the node to be removed is a leaf node, it can be deleted immediately. If the node has one child, the node can be deleted after its parent adjusts a link to bypass the deleted node.

What if the node numbered 2 is deleted?

t à right

set t = t à right

If the node to be removed has two children, the general strategy is to replace the data of this node with the smallest data of the right sub-tree. Then the node with the smallest data is removed (this case is easy since this node cannot have two children).

Remove the numbered 2 again.

C++ implementation for deleting a node

void del(int item) 
{ 
    node *parent,*location; 
    if(root==NULL) 
    { 
        cout<<"Tree empty"); 
        return; 
    } 
    find(item,&parent,&location); 
    if(location==NULL) 
    { 
        cout<<"Item not present in tree"; 
        return; 
    } 
    if(location->lchild==NULL && location->rchild==NULL) 
        case_a(parent,location); 
    if(location->lchild!=NULL && location->rchild==NULL) 
        case_b(parent,location); 
    if(location->lchild==NULL && location->rchild!=NULL) 
        case_b(parent,location); 
    if(location->lchild!=NULL && location->rchild!=NULL) 
        case_c(parent,location); 
    free(location); 
}/*End of del()*/ 
void find(int item,node **par,node **loc) 
{ 
    node *ptr,*ptrsave; 
    if(root==NULL) /*tree empty*/ 
    { 
        *loc=NULL; 
        *par=NULL; 
        return; 
    } 

    if(item==root->info) /*item is at root*/ 
    { 
        *loc=root;  
        *par=NULL; 
        return; 
    } 

    /*Initialize ptr and ptrsave*/ 
    if(item<root->info) 
        ptr=root->lchild; 
    else 
        ptr=root->rchild; 
    ptrsave=root; 

    while(ptr!=NULL) 
    { 
        if(item==ptr->info) 
        { 
            *loc=ptr; 
            *par=ptrsave; 
            return; 
        } 
        ptrsave=ptr; 
        if(item<ptr->info) 
            ptr=ptr->lchild; 
        else 
            ptr=ptr->rchild; 
    }/*End of while */ 

    *loc=NULL; /*item not found*/ 
    *par=ptrsave; 
}/*End of find()*/

Rate this article:

Last updated .

Follow Will.Spencer on
  • nishanth

    for deleting the node75.first we go to right side of 75,check how many chids are there.in this case there are two childs.find the max value put it there in the place of 75 and 75 is placed in the place of max value.finally delete the node75 using free()
    :-*