Deletion in binary search tree

Question

So when I delete in binary search tree, do I need to have like 7 different cases i.e.

Left Leaf;
Right Leaf;
Left child with only left child. //i.e the node to be deleted is the left child of it's parent and it has only left child.
Left Child with only right child.
Right child with only left child.
Right child with only right child.
Node to be deleted has both the children i.e. right and left.

Now when this code is using if-else it gets pretty nasty.. is there any other way of doing this.

Here is my code snippet

if(current->left==NULL && current->right==NULL && current->key<prev->key)   //left leaf
prev->left=NULL;
else if(current->left==NULL && current->right==NULL && current->key>prev->key) // right     leaf
prev->right=NULL;
else if(current->left!=NULL && current->right==NULL && current->key<prev->key) // left     child with one child
prev->left=current->left;
else if(current->left==NULL && current->right!=NULL && current->key<prev->key)
prev->left=current->right;
else if(current->left!=NULL && current->right==NULL && current->key>prev->key)
prev->right=current->left;
else if(current->left==NULL && current->right!=NULL && current->key>prev->key)
prev->right=current->left;
else if(current->left!=NULL && current->right!=NULL)
{
    check=current->right;
    check1=check;
    while(check->left!=NULL)
    {
    check1=check;
    check=check->left;
    }
    *current=*check;
    check1->left=NULL;
}

Sander De Dycker · Accepted Answer · 2011-09-30 05:36:43Z

3

You can keep it a lot simpler than that, and simply restrict yourself to three cases when deleting a node from a BST (binary search tree) :

a node without children (a leaf) : just remove it - nothing special needs to be done
a node with one child : remove it, and move the child in its place
a node with two children : swap it with either its in-order predecessor or successor, and then remove it

The wiki page contains an example of how this could look in code.

Or as a very basic example in C :

if (current->left==NULL && current->right==NULL) {
    /* leaf node */
    bst_replace(current, NULL);
}
else if (current->left==NULL || current->right==NULL) {
    /* node with one child */
    bst_replace(current, ((current->left) ? current->left : current->right));
}
else {
    /* node with two children */
    Node* successor = bst_next(current);
    current->data = successor->data;
    bst_replace(successor, successor->right);
}

edited Sep 30, 2011 at 5:36

answered Sep 30, 2011 at 5:18

Sander De Dycker

16.3k1 gold badge37 silver badges41 bronze badges

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

4 Comments

Kraken Over a year ago

say my node to be removed is the left leaf, now in the parent of the node, i need to know whether it was the left child or the right child, as i'd have to put a null in that place. So wont i need two different cases?

Sander De Dycker Over a year ago

@Karan : If you roll it out, yes, but the point I was trying to make was to abstract these details away, and keep the actual deletion limited to just these three cases. See edit of the answer for an example.

Kraken Over a year ago

maybe i can traverse till the parent only and then check if its child node is the last leaf,then remove it right? No need to reach the node to be deleted it self, and reaching till the parent will reduce around half of those cases?

Sander De Dycker Over a year ago

@Karan : It depends on how you intend to delete nodes. If you want to call the deletion function by passing the actual node that needs to be deleted as parameter, that approach won't work. I've just added some example C code to illustrate how it could look.

Navneet · Accepted Answer · 2011-09-30 05:33:42Z

2

I don't really understand the protocol used for deleting here. You seem to not have a binary 'search' tree (no ordering in the tree).

But to just make the code simple. You could do something like this:

bool b1 = (current->left == NULL);
bool b2 = (current->right == NULL);
bool b3 = (current->key > prev->key);

int decision_case = b1 * 4 + b2 * 2 + b3;

switch(decision_case) {
  case 0: // fill in code here
          break;
  ...
  ...
  case 7: // fill in code here
          break;
}

Also, you should use delete to avoid memory leaks here. Hope that helps.

answered Sep 30, 2011 at 5:33

Navneet

9,89611 gold badges38 silver badges52 bronze badges

Comments

Steve Rowe · Accepted Answer · 2011-09-30 05:14:41Z

1

Deleting a NULL pointer has no ill effect. So, you should be able to do this with no special cases. The basic part is just:

delete current->left;
delete current->right;

answered Sep 30, 2011 at 5:14

Steve Rowe

19.4k9 gold badges54 silver badges82 bronze badges

Collectives™ on Stack Overflow

Deletion in binary search tree

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related