BINARY SEARCH TREE creation

Question

i have written a simple code to create and insert elements into a binary search tree, when i write the code in the following manner, the chaining doesn't seem to happen, can anybody help me understand what exactly is happening in the insert function ? I know the code to insert elements into a binary search tree, just curious to know why this one doesn't work.

#include <stdio.h>
#include<stdlib.h>

struct node {
    struct node *left;
    struct node* right;
    int element;
};

void insert(struct node *node,int x) {
    if(node==NULL) {
        node=(struct node *)malloc(sizeof(struct node));
        node->element=x;
        node->left=NULL;
        node->right=NULL;
    } else {
        if(x<node->element) {
            insert(node->left,x);}
        else {
            insert(node->right,x);
        }
    }
}

void inorder(struct node *base) {
    if(base!=NULL) {
        inorder(base->left);
        printf("%d ",base->element);
        inorder(base->right);
    }
}


int main(int argc, char *argv[]) {
    struct node *base;
    base=(struct node *)malloc(sizeof(struct node));
    base->element=1;
    base->left=NULL;
    base->right=NULL;
    insert(base,25);
    insert(base,30);
    inorder(base);

    return 0;
}

if the insert function is written this way, it works but still doesn't work for creation of the first node of the binary search tree, confused :/

void insert2(struct node *node,int x) {
    if(node==NULL) {
        node=(struct node *)malloc(sizeof(struct node));
        node->element=x;
        node->left=NULL;
        node->right=NULL;
    } else {
        if(x<node->element) {
            if(node->left==NULL) {
                node->left=(struct node *)malloc(sizeof(struct node));
                node->left->element=x;
                node->left->left=NULL;
                node->left->right=NULL;
            } else {
                insert2(node->left,x);
            }
        } else {
            if(node->right==NULL) {
                node->right=(struct node *)malloc(sizeof(struct node));
                node->right->element=x;
                node->right->left=NULL;
                node->right->right=NULL;
            } else {
                insert2(node->right,x);
            }
        }
    }
}

Answer 1

C is pass-by-value. When you pass something into a function's parameter, the function makes a copy of it. So when you pass a struct node pointer into the insert function, C makes a copy of that pointer.

What you did in main is first you made a struct node* base:

base --> struct node.

When you call insert(base, 25), C makes a copy of base. So now in your memory you have something like this:

basecpy ---> [struct node] <--- base

So in your insert, you are essentially doing

if(basecpy==NULL)
    {basecpy=(struct node *)malloc(sizeof(struct node));
    basecpy->element=x;
    basecpy->left=NULL;
    basecpy->right=NULL;}

Which does not change base in anyway at all - it just changes basecpy.

This can be solved by using double pointers:

void insert(struct node **node, int x) {
    if (*node == NULL) {
        *node = malloc(sizeof(*node));
        (*node)->element=x;
        (*node)->left=NULL;
        (*node)->right=NULL;
    } else {
        if (x < (*node)->element) {
            insert(&((*node)->left), x);
        } else {
            insert(&((*node)->right), x);
        }
    }
}

And then to use it, pass in the address of base.

insert(&base, 25);

Pointers can be tricky :)

ideone

Answer 2

When you pass a value to a function in C, you're using pass-by-value. What that means is the value gets copied into another variable which becomes local to the function.

void change(struct node *n) {
    n = 42;
}

int main(void) {
    change(NULL); // change can't change the value of NULL, can it?
}

Now take a look at your insert function... Suppose I call insert(NULL,42);, do you think insert is trying to change NULL? Or is it trying to change some local variable, which your main function can't see?

You know what needs to be done already... Either make your insert function use an extra level of pointer indirection as you've suggested in your comments, or return the root node from insert so that you can propagate the changes made by insert into the data structure stored in main (using the assignment = operator).