Delete nodes from binary search tree, without having parent stored inside the structure

Question

as a n exercise i am working on a binary search tree. I have managed to search through the binary tree, and add nodes, but now that i try to find a way to delete, i seem to be stuck at how to determine who is the parent of a node that is to be deleted.

So to start with i have this structure

struct BST_node {
    struct double_linked_list *data;
    struct BST_node *left;
    struct BST_node *right;
};

and i have also a pointer for this structure that points to root..

struct BST_node *BST_email_root = 0;

I have this function to search for a Node

struct BST_node *BST_find_customer(struct BST_node *root, char *email) {
if (root==NULL)
    return NULL;
if (strcmp(email,root->data->data->email)==0)
    return root;
else
    {
    if (strcmp(email,root->data->data->email)==-1)
    return BST_find_customer(root->left,email);
    else
        return BST_find_customer(root->right,email);
    }

that i call inside other functions, by using

b = BST_find_customer(BST_email_root, email);

and i am trying to create the function to delete nodes..What i have to is this:

struct BST_node *BST_delete(struct BST_node *root, char *email)
    {
    struct BST_node *temp;
    if (root==NULL)
        return root;
    else if(strcmp(root->data->data->email,email)>0)
        root->left = BST_delete(root->left, email);
    else if(strcmp(root->data->data->email,email)<0)
        root->right = BST_delete(root->right, email);
    else
        {
        if(root->left == NULL && root->right == NULL)
            {
            free(root);
            root = NULL;
            }
        else if(root->right == NULL)
            {
            temp = root;
            root = root->left;
            free(temp);
            }
        else if(root->left == NULL)
            {
            temp = root;
            root = root->right;
            free(temp);
            }
        else
            {
            struct BST_node *maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree
            root->data = maxNode->data; //Overwriting the root node with MAX-LEFT
            root->left = BST_delete(root->left, maxNode->data);//deleted the MAX-LEFT node
            }

        return root;
        }

    }

by using this function also

struct BST_node *findMaxNode(struct BST_node *root)
            {
                if(root->right == NULL) return root;
                findMaxNode(root->right);
            }

However this doesnt work also and i get errors

Try keeping a pointer to the previous node you have traversed. — n. m. could be an AI
– n. m. could be an AI, Commented Jan 22, 2017 at 18:05

m.raynal - bye toxic community · Accepted Answer · 2017-01-22 19:29:07Z

1

Here is a solution, although it's not recursive .....

To delete a node N from a BST, you need to consider the 3 cases :

If N is a leaf, then no problem, just delete it
If N has only one son, just replace N by its son ; you'll need the pointer towards the father of N to do that

If N has two sons, then you can replace N by the leftest son of its right son, or by the rightest son of its left son to keep the order properties.

void *BST_delete(struct BST_node *root, char *email){

if (root==NULL)
    return;

struct BST_node * father = NULL;
char which_son; //will help us in remembering if root is the right or left son of his father

while (strcmp(email,root->data->data->email)!=0){ //first, finding root and remembering who's root father
    if(root==NULL) {
         return ;
    } else if (strcmp(email,root->data->data->email) < 0){
         father = root;
         root = root->left;
         which_son = 'l';
    } else {
         father = root;
         root = root->right;
         which_son = 'r';
    }
}
    // now you have both the root node, and its father
if ( (root->right == NULL) && (root->left == NULL) ){ //case 1, if it's a leaf
     free(root);
     return;
} else if (root->left == NULL) { //case 2 
     if (which_son == 'l') {
         father->left = root->right;
     } else {
         father->right = root->right;
     }

} else { //case 3 : here i get the "rightest" son of root's left son
    struct BSD_node * replacing_node = root->left;

    while (replacing_node->right != NULL) {
        replacing_node = replacing_node->right;
    } //now replacing_node is a leaf, and can replace root
    if (which_son == 'l') {
        father->left = replacing_node;
        replacing_node->left = root->left;
        replacing_node->right = root->right;
    } else {
        father->right = replacing_node;
        replacing_node->left = root->left;
        replacing_node->right = root->right;
    }
}
free (root);
}

I changed the return value of your function to void , since it might not need any return value.

It can be implemented in an easier way by simply replacing the 'data' field of one node by another, but i purposely implemented it in that fashion to emphasizes the fact that the node to delete is replaced by one of his descendants.

If it doesn't seem obvious to you that the node to suppress should be replaced by the rightiest (leftiest) son of its left (right) son, then check that these are the only 2 nodes which do not present the risk of breaking the order of your BSD.

Also, this function suffers a lot from being monolithic, it would enjoy being refactorised.

edited Jan 22, 2017 at 19:29

answered Jan 22, 2017 at 18:38

m.raynal - bye toxic community

3,2023 gold badges26 silver badges44 bronze badges

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

3 Comments

ritgeo Over a year ago

Thanks for the answer very much.. I want to return only the BST_EMAIL_root which is just a pointer to the newest node of the binary tree.. I have inserted your code to my full program, however it doesnt seem to work so good... Trying to debug it further now!

m.raynal - bye toxic community Over a year ago

i just corrected the last lines, replacing replacing_node with root in the very last else statement, and added a return which was missing and would provoque a seg_fault ; and yes, i wrote it on the spot, and i'm no expert (yet), so i wouldn't be surprised if a mistake or two remain hidden within, but the spirit of supppressing a node in a binary tree is here. Good luck !

ritgeo Over a year ago

Thank you so much for the help! I am trying now to check my whole code, but though it seems to work..it doesnt really work.. This is driving me nuts :)

Collectives™ on Stack Overflow

Delete nodes from binary search tree, without having parent stored inside the structure

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related