Deleting a node from binary tree

Write a program to delete a node from binary search tree.

Solution :

The problem with binary tree operations is that it is nonlinear. 

When we delete a node from linked list, we link the previous node to the next node so that the list is not broken. But that is not simple in binary tree. Because the node has two next nodes - left child node and right child node. Which do we link to previous node - or parent node? If we link say left child node to the parent of node to be deleted, what do we do with other branch?

When a node is to be deleted from a binary search tree, there are 3 possible cases.

1. the node is leaf
2. the node has only one child/subtree
3. the node has both children/subtrees

The following recursive algorithm takes care of all three cases

1. nd = root
1. find the node to be deleted 
2. if nd->val > delvalue recursively call delete on nd->left and set result to nd->left
3. if nd->val < delvalue recursive, call delete on nd->right and set result to nd->right
2. node is found
1.  if nd->val==delvalue
1. if nd is a leaf node return NULL so that parent->left or parent->right is NULL after deleting nd
2. if nd has only one non-null child, return non-null child. parent->left or parent->right is set to nd->child
3.  If nd has both children, find in order successor of nd.
1.  copy sucessor's value to nd
2. set node to be deleted (nd) to successor
3.  Delete this inorder successor using either a or b above. because successor will be either be leaf or will have only right child

For function in C, you can refer my website

Here is a complete C++ program to create a binary tree and delete a node from the tree. 

#include<iostream>
using namespace std;
struct node
{
   int n;  
   struct node *left;
   struct node *right;
};
class bintree
{
   struct node *root; 
public:
   bintree()
   {
      root = NULL;
   }
   node* createNode(int n)
   {
      node *newnode= new node;
      newnode->n = n;
      newnode->left = NULL;
      newnode->right = NULL;
      return newnode;
   }
   node * insertNode(int n)
   {
      node *nd = createNode(n);
      if(root ==NULL)
         root = nd;
      else
      {
         root = insertRec(nd,root);
         
       }
      return root;
   }
   node *insertRec(node *newnd,node *parent)
   {
      if(parent==NULL)
         return newnd;    
      if(newnd->n>parent->n)
         parent->right = insertRec(newnd,parent->right);
      else if(newnd->n < parent->n)
         parent->left = insertRec(newnd,parent->left);
   }
   void displayTree(node *nd)
   {
          if(nd!=NULL)
          {
             displayTree(nd->left);
	     cout<<" "<<nd->n<<"  ";
             displayTree(nd->right);
          }
   }
   void printTree()
   {
      displayTree(root);
   }
   node* findRightStMin(node*nd);
   node* deleteNode(node *nd,int delval);
   node *deletevalue(int m)
   {
       root = deleteNode(root,m);
   }
    
};
 int main()
{
   bintree tr;
   while(true)
   {
     int n;
     cout<<"Number(-1 to quit):";
     cin>>n;
     if(n==-1)
         break;
     tr.insertNode(n);
   }
   tr.printTree();
   cout<<"Enter the value to be searched:";
   int n;
   cin>>n;
   node* nd = tr.search_node(n);
   if(nd!=NULL)
       cout<<"The node is found";
   cout<<"The number of nodes is "<<tr.count();
}
/* inorder successor is the minimum of 
right subtree*/

node* bintree::findRightStMin(node* nd)
{
     nd = nd->right;
     while(nd->left!=NULL)
       nd = nd->left;
     return nd;
}
node* bintree::deleteNode(node *nd, int delval)
{
    if(nd ==NULL)
       return nd;
    if(nd->n >delval)
        nd->left = deleteNode(nd->left,delval);
     else if(nd->n < delval)
        nd->right = deleteNode(nd->right,delval);
     else/*node found*/
     {
        if(nd->left==NULL && nd->right==NULL)/*leaf node*/
         {
            delete nd;
     	    nd = NULL;
         }
        else if(nd->left==NULL)/*has only right child*/
        {
           node* temp = nd->right;
           delete nd;
           nd =temp;
        }
        else if(nd->right==NULL)/*has only left child*/
        {
           node* temp = nd->left;
           delete nd;
           nd = temp;
        }
        else/*has both subtrees*/
         {
          node * min_node = findRightStMin(nd);
          nd->n = min_node->n;
          nd->right = deleteNode(nd->right,min_node->n);
         }      
      }
    return nd;  
}
int bintree::count_leaf_nodes(node * nd)
{
    if(nd==NULL)
       return 0;
    if(nd->left ==NULL  && nd->right==NULL)
       return 1;
   return 1+count_leaf_nodes(nd->left)+count_leaf_nodes(nd->right);
}
node* bintree::search_node( int num)
{
   node* temp = root;
   while(temp!=NULL)
   {
      if(temp->n>num)
         temp = temp->left;
      else if(temp->n<num)
         temp = temp->right;
      else/*we found a match*/
         return temp;
   }
   return NULL;/*no match*/
}