Skip to main content

Binary tree deletion - non-recursive

In the previous post we have seen how to delete a node of a binary search tree using recursion.

Today we will see how to delete a node of BST using a non-recursive function.

Let us revisit the 3 scenarios here
  1. Deleting a node with no children
    • just link the parent to NULL
  2. Deleting a node with one child
    • link the parent to  non-null child of node to be deleted
  3. Deleting a node with both children
    • select the successor of node to be deleted
    • copy successor's value into this node
    • delete the successor
In order to start, we need a function to search for a node in binary search tree. Did you know that searching in  a BST is very fast, and is of the order O(logn).

To search
  • Start with root
  • Repeat until value is found or node is NULL
    • If the search value is greater than node branch to right
    • If the search value is lesser than node branch to left. 
Here is the function


NODEPTR find_node(NODEPTR root,NODEPTR *parent,int delval)
{
 NODEPTR nd = root;
    NODEPTR pa = root;
     if(root->val==delval)
 {
   *parent = NULL;
          return root;
 }
 while(1 )
 {
   
  if(nd==NULL)
      return NULL;
  
  if(delval < nd->val)
  {
   pa = nd;
   nd = nd->left;    
  }
  else if(delval>nd->val)
  {
   pa = nd;
   nd = nd->right;    
  }  
  else
  {/* we found a match */    
     
      *parent = pa;
      return nd;
  }
  
 }
}

What is this function? Looks complicated? Not really. We have just added some codes to find the parent also. Remember we need parent of the node to be deleted too. Before we branch to left or to right, we set current node as parent.

Next we have to write deletion function


NODEPTR delete_non_recursive( NODEPTR root,NODEPTR delnode,NODEPTR parent)
{
 NODEPTR pa;
  
 if (delnode->left!=NULL && delnode->right!=NULL)/*has both subtrees*/
  {
   
   NODEPTR succ = find_rightst_min(delnode,&parent);
   delnode->val = succ->val;
   delnode=succ;
  }
 if (delnode->left!=NULL)
 {
  /*has only left child*/
  if(parent==NULL){
                       /*we are deleting root*/
   root = delnode->left;
  }else
  {
   if(parent->left ==delnode)
    parent->left = delnode->left;
   else
    parent->right = delnode->left;
  }
  free(delnode);
 }
 else if(delnode->right!=NULL)
 {/*has only right subtree*/
  if(parent==NULL)/*we are deleting root*/
  {
   root = delnode->right;
  }
  else{
   /*has only right child*/
   if(parent->left==delnode)
    parent->left = delnode->right;
   else
    parent->right = delnode->right;
  }
  free(delnode);
 }
 else{ 
   
     /* leaf node */
   if(parent==NULL)
   {
    root = NULL;
   }
   else{
    if(parent->left==delnode)
    {
       parent->left = NULL;
     free(delnode);
    }
    else
    {
     parent->right = NULL;
     free(delnode);
    }
   }
  }
     return root;
}

The special case here is what about deletion of root? If we delete the root, there is no parent. Parent has been set to NULL in find_node function for this case. So in each of the 3 scenarios, we check if parent is null. If parent is null then root is reconfigured to either a non-null child of node to be deleted or to null if root is the only node in the tree.

Now it is time for complete program.


#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR; 

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
}

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
}

void pre_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        printf("%d---",nd->val);   
        pre_order(nd->left);
        pre_order(nd->right);
            
     }
}

void post_order(NODEPTR nd)
{
   if(nd!=NULL)
    {    
 post_order(nd->left);
        post_order(nd->right);
        printf("%d---",nd->val);
     }
}


/*go left till you reach null*/
NODEPTR find_rightst_min(NODEPTR nd,NODEPTR *parent)
{
     NODEPTR pa = nd;
     nd = nd->right;
     while(nd->left)
     {
        pa = nd;
        nd = nd->left;
      }
      *parent = pa;
      return nd;
}
 

NODEPTR find_node(NODEPTR root,NODEPTR *parent,int delval)
{
 NODEPTR nd = root;
    NODEPTR pa = root;
     if(root->val==delval)
 {
   *parent = NULL;
          return root;
 }
 while(1 )
 {
   
  if(nd==NULL)
      return NULL;
  
  if(delval < nd->val)
  {
   pa = nd;
   nd = nd->left;    
  }
  else if(delval>nd->val)
  {
   pa = nd;
   nd = nd->right;    
  }  
  else
  {/* we found a match */    
     
      *parent = pa;
      return nd;
  }
  
 }
}
 
NODEPTR delete_non_recursive( NODEPTR root,NODEPTR delnode,NODEPTR parent)
{
 NODEPTR pa;
  
 if (delnode->left!=NULL && delnode->right!=NULL)
  {
   
   NODEPTR succ = find_rightst_min(delnode,&parent);
   delnode->val = succ->val;
   delnode=succ;
  }
 if (delnode->left!=NULL)
 {
  /*has only left child*/
  if(parent==NULL){
   root = delnode->left;
  }else/*we are not deleting root*/
  {
   if(parent->left ==delnode)
    parent->left = delnode->left;
   else
    parent->right = delnode->left;
  }
  free(delnode);
 }
 else if(delnode->right!=NULL)
 {
  if(parent==NULL)/*we are deleting root*/
  {
   root = delnode->right;
  }
  else{
   /*has only right child*/
   if(parent->left==delnode)
    parent->left = delnode->right;
   else
    parent->right = delnode->right;
  }
  free(delnode);
 }
 else{ 
   
     /* leaf node */
   if(parent==NULL)
   {
    root = NULL;
   }
   else{
    if(parent->left==delnode)
    {
       parent->left = NULL;
     free(delnode);
    }
    else
    {
     parent->right = NULL;
     free(delnode);
    }
   }
  }
     return root;
}

    
int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
      
       
       while(1){ 
  NODEPTR search_node,parent;   
   printf("Enter node to be searched(-1 to stop)");
         scanf("%d",&n);
  if(n==-1)
   break;
  search_node = find_node(root,&parent,n);
  if(search_node!=NULL){ 
            root = delete_non_recursive(root,search_node,parent);
   if(root==NULL)
   {
    printf("Now tree is empty");
    break;
   }
   else{
             printf("now tree is");
    in_order(root);printf("\n");
   }
  }else{
     printf("Node not found");
  } 
       } 
       return 0;
}

Happy binary trees :)
Labels:

Comments

Post a Comment

Popular posts from this blog

Linked list in C++

A linked list is a versatile data structure. In this structure, values are linked to one another with the help of addresses. I have written in an earlier post about how to create a linked list in C.  C++ has a library - standard template library which has list, stack, queue etc. data structures. But if you were to implement these data structures yourself in C++, how will you implement? If you just use new, delete, cout and cin, and then claim it is your c++ program, you are not conforming to OOPS concept. Remember you have to "keep it together". Keep all the functions and variables together - in a class. You have to have class called linked list in which there are methods - append, delete, display, insert, find, find_last. And there will also be a data - head. Defining node We need a structure for all these nodes. A struct can be used for this purpose, just like C. struct node { int val; struct node * next; }; Next we need to define our class. W
Post a Comment
Read more

Swap nodes of a linked list

Qn: Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7 Image from: https://tekmarathon.com Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well. So let us try to understand how to go about it. Take two adjacent nodes p1 and p2 Let prevnode be previous node of p1 Now link prevnode to p2 Link p2 to p1 Link p1 to next node of p2 So the code will be prevnode -> next = p2; p1 -> next = p2 -> next; p2 -> next = p1; But what about the start node or head? head node does not have previous node If we swap head with second node, modified head should be sent back to caller  To take care of swapping first and second nodes, we can write p1 = head; p2 = head -> next; p1 -> next = p2 -> next; p2 -> next = p1; head = p2;  Now we are read
Post a Comment
Read more