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

Question

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;  

}

*rootRef = tmp->left; you do keep the left pointer, but the ->right pointer will be orphanased, including the complete right subtree. — wildplasser
– wildplasser, Commented Apr 24, 2014 at 18:13
You can google for pseudocode, for this function. Currently you have maybe 15% of delete node logic. You need pointer to parent of the node you want to delete, and when you delete, you have 3 use cases. 1. Node to be deleted is a leaf 2. Node to be deleted has one child 3. Node to be delted has two children. read this — Dabo
– Dabo, Commented Apr 24, 2014 at 18:40

John Bupit · Accepted Answer · 2014-04-24 19:26:05Z

1

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:

If rootRef has no children, i.e., rootRef->left == NULL && rootRef->right == NULL, simply remove the node.
If rootRef has only one child, replace rootRef with that child.
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;  
}

edited Apr 24, 2014 at 19:26

answered Apr 24, 2014 at 18:01

John Bupit

10.7k10 gold badges45 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

user3366369 Over a year ago

So I should do some if statements after *rootRef = tmp->left;?

John Bupit Over a year ago

That statement is incorrect. You need to implement the deletion algorithm, by handling those 3 cases independently.

user3366369 Over a year ago

Okay so I did that and something is still wrong...I'm pretty sure it has to do with the two child case but I don't know how to recursively check for the children of the child...

user3366369 Over a year ago

Help please! I am very stuck on this

John Bupit Over a year ago

How does (rootRef->left->left == NULL && rootRef->right->right == NULL) mean that rootRef has only 1 child?

|

Collectives™ on Stack Overflow

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

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related