Mar 24, 2012

Remove a node from Binary Search Tree

C++
A node can be removed from a Binary Search Tree using two approaches.
1. Double Pointer Approach
2. Single Pointer Approach

1. Double pointer approach
Getting successor node is the trickiest part when using this approach
void remove(BinaryTreeNode **node, int data)
   {
      if(*node == NULL)
      {
        std::cerr << "ERROR: Node does not exist\n";
      }

      if(data == (*node)->data)
      {
        if((*node)->right == NULL)
        {
          *node = (*node)->left;
        }
        else if((*node)->left == NULL)
        {
          *node = (*node)->right;
        }
        else
        {
          BinaryTreeNode **successor = getSuccessor(&(*node)->left);
          (*node)->data = (*successor)->data;
          remove(successor, (*successor)->data);
        }
      }
      else if(data < (*node)->data)
      {
        remove(&(*node)->left, data);
      }
      else
      {
        remove(&(*node)->right, data);
      }
   }

   //Tricky
   BinaryTreeNode** getSuccessor(BinaryTreeNode **node)
   {
     BinaryTreeNode **tmp = node;
     while((*tmp)->right != NULL)
       tmp = &(*tmp)->right;
     return tmp;
   }

2. Single pointer approach
Note the difference between single pointer and double pointer approach. The difference help in clarifying how pointers work in C/C++
BinaryTreeNode* remove(BinaryTreeNode *node, int data)
   {
     if(node == NULL)
     {
       std::cerr << "ERROR: Node does not exists\n";
       return node;
     }

     if(data == node->data)
     {
       BinaryTreeNode *retval = NULL;
    
       if(node->left == NULL)
       {
         retval = node->right;
         delete node;
         return retval;
       }
       else if(node->right == NULL)
       {
         retval = node->left;
         delete node;
         return retval;
       }
       else
       {
          BinaryTreeNode *successor = getSuccessor(node->left);
          node->data = successor->data;
          node->left = remove(node->left, successor->data);
       }
     }
     else if(data < node->data)
     {
       node->left = remove(node->left, data);
     }
     else
     {
       node->right = remove(node->right, data);
     }

     return node;
   }

   BinaryTreeNode* getSuccessor(BinaryTreeNode *node)
   {
     while(node->right != NULL)
       node = node->right;
     return node;
   }
Java
Java does not have pointers. It has only references which are similar to single pointers in C/C++. Use single pointer approach below to remove a node from Binary Search Tree in Java
private BinaryTreeNode remove(BinaryTreeNode node, int data)
  {
    if(node == null)
    {
      System.out.println("ERROR: Number does not exist");
      return null;
    }

    if(data == node.data)
    {
      if(node.left == null)
      {
        return node.right;
      }
      else if(node.right == null)
      {
        return node.left;
      }
      else //both the children exists
      {
        BinaryTreeNode successor = getSuccessorNode(node.left);
        node.data = successor.data;
        node.left = remove(node.left, successor.data);
      }
    }
    else if(data < node.data)
    {
      node.left = remove(node.left, data);
    }
    else
    {
      node.right = remove(node.right, data);
    }

    return node;
  }

  private BinaryTreeNode getSuccessorNode(BinaryTreeNode node)
  {
    while(node.right != null)
    {
      node = node.right;
    }
    return node;
  }

5 comments :

Anonymous said...

Thanks, very helpful!

Anonymous said...

Very helpful
I appreciate it

Anonymous said...

Good to see implementation in c++ and java. It clear my doubt.

Unknown said...

Best Java example of deleting Binary Search Tree Node!

Gajendra SB said...

Where are you deleting(freeing) the node in double pointer method?

Post a Comment