1

I have a BST and I want to add/delete/find/inorder_traversal/... on it. But when I want to delete an item, there is a problem.

initialize tree:

node_t *init() {
    node_t *node = calloc(1, sizeof(node_t));
    node->left = NULL;
    node->right = NULL;
    node->data = NULL;
    return node;
}

add() function:

int add(node_t *node, void *data) {
    if (node->data == NULL) { //first time when there is only root node exists
        node->data = data;
        printf("%d -> %p\n", (int)node->data, node);
        return 0;
    }
    node_t *prev = NULL, *ptr;
    ptr = node;
    char type;
    while (ptr) {
        prev = ptr;
        if (data < ptr->data) {
            ptr = ptr->left;
            type = 'l';
        } else
        if (data > ptr->data) {
            ptr = ptr->right;
            type = 'r';
        }
    }
    if (type == 'l') {
        node_t *node = calloc(1, sizeof(node_t));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        prev->left = node;
        printf("%d -> %p\n", (int)node->data, node);
        return 1;
    } else
    if (type == 'r') {
        node_t *node = calloc(1, sizeof(node_t));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        prev->right = node;
        printf("%d -> %p\n", (int)node->data, node);
        return 1;
    }
    return -1;
}

del() function:

int del(node_t *node, void *data) {
    if (data < node->data) {
        del(node->left, data);
    } else
    if (data > node->data) {
        del(node->right, data);
    } else
    if (data == node->data) {
        if (node->left == NULL && node->right == NULL) {  // leaf node
            free(node);
            return 0;
        } else
        if (node->left != NULL) {       //node has only left child
            node->data = node->left->data;
            node->left->data = 0;
            free(node->left);
            return 0;
        } else
        if (node->right != NULL) { //node has only right child
            node->data = node->right->data;
            node->right->data = 0;
            free(node->right);
            return 0;
        } else
        if (node->left != NULL && node->right != NULL) { // node has two children
            node_t *temp = min_value(node->right);
            node->data = temp->data;
            del(node->right, data);
            return 0;
        }
    }
    return -1;
}

main():

int main() {
    node_t *tree;
    tree = init();
    add(tree, (void*)40);
    add(tree, (void*)10);
    add(tree, (void*)30);
    add(tree, (void*)25);
    add(tree, (void*)50);
    add(tree, (void*)11);
    add(tree, (void*)76);

    preorder_traversal(tree);
    printf("\n");
    del(tree, (void*)30);
    preorder_traversal(tree);
    printf("\n");
    return 0;
}

before deleting, I run inorder_traversal(), then delete number 30, and again run inorder_traversal(), but the output is as below:

40 10 11 25 30 50 76
40 10 11 0 25 50 76

Guys I would appreciate if you help me.

Also, min_value() function is as below:

node_t *min_value(node_t *node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}
5
  • Good to add min_value() code in the post Commented Mar 31, 2020 at 6:45
  • Are you sure data is present in your tree ? If not you have to check node is not NULL at the beginning because the two first cases can reach the end of a branch. Why else if (data == node->data){ rather than else when you know it is not < nor > ? Same thing for else if(node->left != NULL && node->right != NULL){ when you know both are not NULL because of tests before Commented Mar 31, 2020 at 6:45
  • So according to your assumption, You're saying that my add() function might have insertion problem ? Commented Mar 31, 2020 at 6:50
  • @ShridharRKulkarni Added to the question sir Commented Mar 31, 2020 at 6:52
  • @bruno done sir. Commented Mar 31, 2020 at 7:02

1 Answer 1

2

When you free nodes in del you let them in the tree so later when you access them in preorder_traversal or a new call of del etc you have an undefined behavior.

When you free a node you have to remove it from the tree.

You also suppose the data to remove is present in the tree, if this is not the case the two first cases will reach the end of a branch and you will dereference NULL with bad consequences. You need first to check if node is NULL to return

Also in

   else if(node->left != NULL){       //node has only left child

you do not know if node->right is NULL or not, your assumption node has only left child is false

In init you set a first node without data, that has no sense.

I encourage you to modify your add/del function to get a node ** rather than a node allowing you to modify the tree/variable memorizing the root

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.