CODEWITHSUNDEEP
cbinary-search-tree
Moi
Moi

Reputation: 53

My bst insertion keeps on overriding recently added value in C

it seems to me that I may be overlooking something in my code but please help me see it. Whenever I call this function to insert a new node, it keeps on overriding the most recent node. 

node_t *node_insert(node_t *cur, char name[]){
    int diff = -1;
    if(cur == NULL) {                 
        node_t *new_node = (node_t*)malloc(sizeof(node_t)); 
        strcpy(new_node->name, name);          // copy data
        new_node->right = new_node->left = NULL;                    
        return new_node;                          `
    } else {
       diff = strcmp(name, cur->name); 
       if(diff<0){
          return node_insert(cur->left,name );}
       else if(diff>0){
         return node_insert (cur->right,name );}
       else if (diff ==0) {               
           return NULL;
        }
    }
}

The function above is then called down below as such:

int bst_insert(bst_t *tree, char name[]){
    node_t *result = node_insert(tree->root, name); // update node
    if(result == NULL) {            // duplicate found, ignore
        return 0;                   // 0 indicates not modified
    } else {       
        tree->root = result;       
        tree->size++;               // size now larger
        return 1;                   // 1 indicates modifed
    }
}

Upvotes: 1

Views: 98

Answers (1)

Pablo
Pablo

Reputation: 13570

Like I said in the comments, tree->root = result; is correct only when tree->root is NULL, that means when the tree is empty. After that you've constantly updating the root node with the new node, thus forgetting the old tree.

Your node_insert function creates a new node_t object, that's OK. Then you do the recursion, you find the spot where you would have to insert the new node, but you just return the new node without adding. The information where to add the new node is lost.

You only have to modify your node_insert a little bit:

int node_insert(node_t **cur, char name[]) {
    int diff = -1;
    if(*cur == NULL) {                 
        node_t *new_node = calloc(1, sizeof *new_node);
        if(new_node == NULL)
            return 0;

        strcpy(new_node->name, name);
        *cur = new_node;
        return 1;
    } else {
       diff = strcmp(name, (*cur)->name); 
       if(diff<0){
          return node_insert2(&((*cur)->left),name);}
       else if(diff>0){
         return node_insert2(&((*cur)->right),name);}
       else if (diff ==0) {               
           return 0;
        }
    }
}

Now you have to pass a double pointer to a node_t object. If *cur is NULL, then you create a new node_t object and assign it to *cur, thus changing the location (to the newly created object) where the original pointer was pointing to.

In the recursion it is only a matter of passing a pointer to the left pointer and right pointer. If the recursion finds the right node and left (or right depending on the value of diff), then you pass a pointer to the pointer to the next recursion, where *cur will be NULL and the new node will be appended to.

Bear in mind that the way you create a new bst_t tree is important, tree->root must be initialized with NULL, otherwise the node_insert function will fail with undefined behaviour when it is doing the recursion.

Note how I create a new node. I use calloc because it initialized the new memory to 0, thus new_node->left and new_node->right will point to NULL. There is one thing I don't like about your creation of a new node though:

strcpy(new_node->name, name);

Since we haven't seen how you declared the structs, it's difficult to know if that's correct. If node_t->name is a char*, then you would need to allocate memory for that and then do strcpy:

new_node->name = calloc(strlen(name) + 1, 1);
if(new_node->name == NULL)
{
    free(new_node);
    return 0;
}

strcpy(new_node->name, name);

or if your system has strdup

new_node->name = strdup(name);
if(new_node->name == NULL)
{
    free(new_node);
    return 0;
}

But if node_t->name is a char[SOME_LENGTH], the strcpy is not the right choice, because you have no guarantee that the string in name is shorter than SOME_LENGTH - 1. In this case you would have to use strncpy and make sure that you end up with a valid string:

strncpy(new_node->name, name, sizeof new_node->name);
new_node->name[sizeof(new_node->name) - 1] = 0;

And of course you don't have to forget to free the memory you've allocated.

Now you can update your bst_insert to:

int bst_insert(bst_t *tree, char name[]){

    int ret = node_insert(tree->root, name);

    if(ret)
        tree->size++;

    return ret;
}

Upvotes: 1

Related Questions