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()*/