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

Introduction to AVL tree

AVL tree is a balanced binary search tree where the difference between heights of two sub trees is maximum 1. Why balanced tree A binary tree is good data structure because search operation here is of the order of O(logn). But this is true if the tree is balanced - which means the left and right subtrees are almost equal in height. If not balanced, search operation will take longer.  In worst case, if the tree has only one branch, then search is of the order O(n). Look at this example.  Here all nodes have only right children.  To search a value in this tree, we need upto 7 iterations, which is O(n). So this tree is very very inefficient. One way of making the tree efficient is to, balance the tree and make sure that height of two branches of each node are almost equal. Height of a node Height of a node is the distance between the node and its extreme child.  In the above a diagram, height of 37 is 3 and height of left child of 37 is 0 and right child of 37 is 2. Bal...
Post a Comment
Read more

Balanced brackets

Have you observed something? When ever you are writing code using any IDE, if you write mismatched brackets, immediately an error is shown by IDE. So how does IDE  know if an expression is having balanced brackets? For that, the expression must have equal number of opening and closing brackets of matching types and also they must be in correct order. Let us look at some examples (a+b)*c+d*{e+(f*g)}   - balanced (p+q*[r+u )] - unbalanced (p+q+r+s) ) - unbalanced (m+n*[p+q]+{g+h}) - balanced So we do we write a program to check if an expression is having balanced brackets? We do need to make use of stack to store the brackets. The algorithm is as follows Scan a character - ch from the expression If the character is opening bracket, push it to stack If the character is closing bracket pop a character from stack If popped opening bracket and ch are not of same type ( ( and ) or [ and ] ) stop the function and return false Repeat steps 2 and 3 till all characters are scanned. On...
2 comments
Read more

Program to delete a node from linked list

How do you remove a node from a linked list? If you have to delete a node, first you need to search the node. Then you should find its previous node. Then you should link the previous node to the next node. If node containing 8 has to be deleted, then n1 should be pointing to n2. Looks quite simple. Isn't it? But there are at least two special cases you have to consider. Of course, when the node is not found. If the node is first node of the list viz head. If the node to be deleted is head node, then if you delete, the list would be lost. You should avoid that and make the second node as the head node. So it becomes mandatory that you return the changed head node from the function.   Now let us have a look at the code. #include<stdio.h> #include<stdlib.h> struct node { int data; struct node * next; }; typedef struct node * NODEPTR; NODEPTR create_node ( int value) { NODEPTR temp = (NODEPTR) malloc( size...
3 comments
Read more