CODEWITHSUNDEEP
cbinary-search-treetreenode
user3366369
user3366369

Reputation: 13

Remove data from binary search tree pointed to by pointer of root

I am having a lot of trouble figuring out how to remove data from a BST using a double pointer and then changing the root if needed. This is what I am trying but when I test it it removes numbers that should not be removed...any idea on what is flawed?

EDIT: Below is my new code after the answer...

    int removeBST(struct TreeNode** rootRef, int data)
    {

      while (*rootRef && (*rootRef)->data != data)
      {

         if ((*rootRef)->data > data)
         {

             rootRef = &(*rootRef)->left;
         }
         else if ((*rootRef)->data < data)
         {
              rootRef = &(*rootRef)->right;
         }
     }

    if (*rootRef)
    {
        struct TreeNode *tmp = *rootRef;
        if (rootRef->left == NULL && rootRef->right == NULL) // no children
        {
        free(tmp);
        }
        else if (rootRef->left->left == NULL && rootRef->right->right == NULL) // one child
{
  rootRef = rootRef->left;
}
else
{
  rootRef = inOrderSuccessor(rootRef);
  removeBST(**rootRef, data);
}

        return 1;
    }

    return 0;  

}

Upvotes: 0

Views: 1528

Answers (1)

John Bupit
John Bupit

Reputation: 10618

I think the problem lies in the line *rootRef = tmp->left;.

This line attempts to delete the node rootRef. What it actually does is simply replaces the node with its left child, which is correct if rootRef only has a left child. If it has a right childe, however, it will become an orphan.

What you need to do is handle the deletion properly, as follows:

  1. If rootRef has no children, i.e., rootRef->left == NULL && rootRef->right == NULL, simply remove the node.

  2. If rootRef has only one child, replace rootRef with that child.

  3. If rootRef has two children, replace the value of rootRef with its in-order successor, and then delete that node recursively, until you reach case 1 or 2.

An example on removing a node from a BST.

Your code must look something similar to this:

int removeBST(struct TreeNode** rootRef, int data) {
    while (*rootRef && (*rootRef)->data != data) {
        ...
    }


    struct TreeNode* prootRef = *rootRef;
    if (prootRef) {
        if(prootRef->left && prootRef->right) // Both children exist
            // Find its in-order successor
            ...
        }
        else if(prootRef->left) { // Only left child exists
           // Replace rootRef by its left child
           ...
        }
        else if(prootRef->right) { // Only right child exists
           // Replace rootRef by its right child
           ...
        }
        else { // rootRef is a leaf node
           // Delete rootRef
           ...
        }

        return 1;
    }

    return 0;  
}

Upvotes: 1

Related Questions