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

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    2 comments
    1. Tikhon

      22 June, 2017 at 2:19 pm

      what does functions case_a, case_b & case_c do?

      Reply
    2. nishanth

      20 August, 2010 at 10:31 am

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

      Reply
    C
    } 235 queries in 0.389 seconds.