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);
            }
        }
    }
}

In `insert()`, you are just modifying the local `node` variable while creating a new node. — Kishore, Apr 04 '15 at 13:10
[Please don't cast the return value of `malloc`](http://c-faq.com/malloc/mallocnocast.html)... — autistic, Apr 04 '15 at 13:10
I totally understand that you're having a hard time debugging your code. Start by putting the code into a readable form (indentation, placement of braces etc). Then either use a debugger or put more printf's to understand the flow of the program. — stefan, Apr 04 '15 at 13:11
@stefan, i just have one problem in the question, the code is pretty understandable, the way the pointers behave is what confuses me in this one — codemania23, Apr 04 '15 at 13:15
in `node=(struct node *)malloc(sizeof(struct node));`, you are assigning the address of the newly allocated space to the local variable `node`. So once the control goes out of your function, you won't have access to it. Now, that's a memory leak. — Kishore, Apr 04 '15 at 13:19
@Kishore, how to correct it or how to relate it to the pointer in the calling function ? — codemania23, Apr 04 '15 at 13:23
@undefinedbehaviour, i didnt't get you, if i don't cast it, hw will it be a pointer of type struct node* ?,btw thanks for editing, i deleted that answer — codemania23, Apr 04 '15 at 13:26
The conversion between `void *` and `struct node *` is implicit when you use a C compiler, so there is no need for an explicit conversion. If you're not using a C compiler, then you're not programming in C. See [this question](http://stackoverflow.com/q/605845/2173917) for more information. — autistic, Apr 04 '15 at 13:29
@undefinedbehaviour , ok i'll remove it, but what about relating *node to *base, what should i do about that ? is there a way ? or will I have to compulsorily use a double pointer ? — codemania23, Apr 04 '15 at 13:34

score 1 · Accepted Answer · answered Apr 04 '15 at 13:44

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).

Keith Yong · Answer 2 · 2015-04-04T13:56:46.203

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

BINARY SEARCH TREE creation

2 Answers2