0

I am making a basic binary search tree and its operations.

Why isn't my insert working?

It is not taking in the values and the root that I am sending from the main does not get associated to the values I insert.

void insert(struct bst* root, int val)
{
    if (root == NULL)
    {
        struct bst* temp = malloc(sizeof(struct bst));
        temp->val = val;
        temp->left = NULL;
        temp->right = NULL;
        root = temp;
    }
    else
    {
        if (root->val > val)
        {
            insert(root->left,val);
        }
        else if (root->val < val)
        {
            insert(root->right,val);
        }
        else
        {
            printf("alredy exits");
        }
    }
}
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Cygnus
  • 1
  • 2

1 Answers1

1

If you want the value of root to be known after the function returns, you need to change the prototype to

void insert(struct bst** root, int val)

And pass the address of root when you call it. Then you change the line

root = temp;

to

*root = temp;

and of course you need to change the other accesses to root in your code. Might be better to call the parameter of the function root_p (for pointer to root) and then dereference it (once you have determined it is not NULL) with

root = *root_p;

That makes the entire function something like this:

void insert(struct bst **root_p, int val)
{
    if (*root_p == NULL)
    {
        struct bst* temp = malloc(sizeof(struct bst));
        temp->val = val;
        temp->left = NULL;
        temp->right = NULL;
        *root_p = temp;
    }
    else
    {
        root = *root_p;
        if (root->val > val)
        {
            insert(&(root->left),val);
        }
        else if (root->val < val)
        {
            insert(&(root->right),val);
        }
         else
        {
             printf("already exists"); // <<<<< fixed typo here
        }
    }
}

In the calling function you would have

struct bst *root;
for(int ii=0; ii<5; ii++) insert(&root, 1); // for example

edited following @whozcraig's comment

Floris
  • 45,857
  • 6
  • 70
  • 122
  • Thanks, i am new to c can you please explain why you are using a pointer to take in the structure and i have read the second implementation of the same thing in which the function is of the type of a structure. Why doesn't that use a pointer like this one. – Cygnus Apr 13 '14 at 05:43
  • Not really enough space for a good explanation… If you have a pointer to a structure (`root`), and you want to assign a value to that pointer, you need to know where that pointer is stored. Thus, you need the _address_ of the pointer. This is `&root`, and the type is "a pointer to a pointer". Which is how you end up with the `**`. – Floris Apr 13 '14 at 05:48
  • Note: Your insert recursions should be using the *address* of the left and right pointers respectively. Right idea though. And a non-recursive solution [can be found here](http://pastebin.com/cRWyYnE4). – WhozCraig Apr 13 '14 at 07:38
  • @whoscraig - well spotted. Was late here. Better now? – Floris Apr 13 '14 at 12:54