Thread: Binary Search Tree

Hello :)

I have to write a C-code for a binary search tree.
It will read from a textfile and create with it a tree. When I execute the file I should have all data from the file in the tree and it should print the numbers in order. I should probably mention that this is a phone book so there is not only a number but also a name.
So far, my program only prints three numbers, without the name. I tried several solutions and debugs and realized that the issue is in the insert function. I cannot change the function, which is a given void function, and therefore I can't use recursion. The three numbers are inorder though!
If there is a number twice, the program is supposed to return but I tried a lot of places and can't find where I should put this condition.
Also, according to my printf-debugging my program reads everything from the textfile but doesn't print it.
I have been sitting on it for a whole week, always spending several hours on the computer in front of my code. It would be awesome if someone could help me here :)
I would rather have someone point mistakes out instead of just sending me back my whole code that is already adjusted because I really want to understand what doesn't work :)

Code:

void bst_insert_node(bstree* bst, unsigned long phone, char *name) 
{

        bst_node* node = malloc(sizeof(bst_node));
        node->phone = phone;
        node->name = name;
        node->parent = NULL;
        node->left = NULL;
        node->right = NULL;

        bst_node* tmp = malloc(sizeof(bst_node));
        tmp->phone = phone;
        tmp->name = name;
        tmp->parent = NULL;
        tmp->left = NULL;
        tmp->right = NULL;

while (tmp != NULL)
{
        node->parent = tmp;

        if(node->phone < tmp->phone)
        {
        tmp = tmp->left;
        }

        else
        {
        tmp = tmp->right;
        }
}

node->parent = bst->root;

if(node->parent == NULL)
{
        bst->root = node;
}

else 
{
        if(node->phone < node->parent->phone)
        {
             node->parent->left = node;
        }

        else
        {
        node->parent->right = node;
        }   
      
bst->count++;
}
}

Originally Posted by laserlight

At the moment you have a memory leak in that you malloc space for tmp, but never free it. Perhaps tmp should be initialised to bst->root instead: your limited insertion problem is due to the fact that tmp->left and tmp->right are null pointers, so the loop ends pretty quickly.

Hi, thanks for the answer! :)
I changed my tmp to this:

Code:

bst_node* tmp = malloc(sizeof(bst_node));
        tmp = bst->root;
        tmp->phone = phone;
        tmp->name = name;
        tmp->parent = NULL;

But now I have en error regarding the memory in the line

Code:

tmps->phone = phone;

When I marked it as a comment, the error just went to the next line.


I thought that all my memory got free'd when I delete the tree

Code:

void bst_free_subtree(bst_node* node) 
{
     if (node != NULL)
     {
        bst_free_subtree(node->left);
        bst_free_subtree(node->right);
        free(node);
     }
}

but I see that I need another "free" just for tmp. Should that be at the end of the insert function? After bst->count++; ?
I tried that several times in multiple places but it seems my program doesn't even get there.

Okay, so if that is wrong then I deleted it and compiled again after I added before the while loop:

Code:

if(bst->root == NULL)
{
   return;
}

If I get NULL as an argument then I don't want to insert (correct me if I am wrong).
In fact, now I only have a memory leak because it says:

HEAP SUMMARY:
==9100== in use at exit: 5,040 bytes in 126 blocks
==9100== total heap usage: 132 allocs, 6 frees, 11,976 bytes allocated

Up to now (and I still think this way) I believe this is because I allocate every single phone number but the post-order function doesn't free all of it since apparently it doesn't receive all those numbers. Or is that totally wrong?

Unfortunately, now I have no output whatsoever
I feel like I looked at this code for so long that I don't even know what I am doing anymore...

Oh my god, that was perfect! I understood it finally, thank you so much!
My function finally works, I am so happy!