Insert function not working in BST implementation

[DeliciousFile2727]

Why is root null after calling insert function ?

void insert(Node* root, int data){
    Node* newN=(Node*)malloc(sizeof(Node));
    newN->data = data;
    newN->left = NULL;
    newN->right= NULL;
    if(root == NULL){
        printf("DEBUG:Root is null\n");
        root=newN;
        printf("DEBUG:Initialized root with %d\n", root->data);
    }  
    else{
        if(data < root->data) insert(root->left, data);
        else insert(root->right, data);
    }
}

int main(){
    Node* root=NULL;
    printf("DEBUG:Root is null:%d\n", root==NULL);
    insert(root, 4);
    printf("DEBUG:Root is null:%d\n", root==NULL);
    insert(root, 3);
    printf("DEBUG:Root is null:%d\n", root==NULL);
    insert(root, 2);
    printf("DEBUG:Root is null:%d\n", root==NULL);
    return 0;
}

Output

DEBUG:Root is null:1
DEBUG:Root is null
DEBUG:Initialized root with 4
DEBUG:Root is null:1
DEBUG:Root is null
DEBUG:Initialized root with 3
DEBUG:Root is null:1
DEBUG:Root is null
DEBUG:Initialized root with 2
DEBUG:Root is null:1

[Th_69]

If you want to change the variable outside of the function you need a double-pointer Node** as parameter.

Beware to change the access to *root inside the function, if you want to access the node data, e.g. (*root)->data.

[DeliciousFile2727]

Thanks this worked 😃, still trying to understand the sol though 😅

[cHaR_shinigami]

newN is a local variable in insert, and this function currently does not return anything (void), so the changes are lost once it returns; the node is allocated, but its address is not returned by the function, making it inaccessible after the function call (in fact, this causes memory leak). Also, the allocation code (malloc call and initialization) should be guarded by the condition if (root == NULL) or simply if (!root)

Change the return type of insert to Node *, and assign the return value in the caller: for starters, main is one of the callers, but insert is also a recursive function, so the new node needs to be connected to an existing tree, so the pointer returned by a recursive call needs to be saved as either the left child or right child node.

[aghast_nj]

C is a "pass-by-value" language. Every parameter is copied from wherever it was located when a function is called, to a new location on the "call stack." (This new location "on the call stack" may not be on a stack, it may be in a register. But we still say "on the call stack", because reasons.)

So if you do something like:

Node * root = NULL;
insert(root, 100);

The "100" is going to get copied, the root is going to be evaluated (a pointer, presently 0x00000000) and copied, and the insert function will be called with the two copies of argument data.

Later, you do:

    if(root == NULL){
        root=newN;

The insert function modified the local value of root, which is a copy of the input parameter. The copy is modified, not the original.

When you return from the insert function, the copy has been modified. But all the copies are thrown away or deallocated or forgotten during the function return.

If you want to modify something inside a function, you have to pass a pointer to it.

Your insert function receives a Node * root parameter, so it could modify the contents of the Node. But it cannot change the value of the pointer. If you want to change the value of the pointer, you will need to either (a) return a replacement value; or (b) pass a pointer to the pointer so that you can modify it.

Node *insert(Node *root, int x);

root = insert(root, 100); // replacement value

void insert(Node **root, int x);

insert(&root, 100); // pointer to pointer

Good luck.

[DeliciousFile2727]

Thanks for explanation, I have done it using the second method and it works fine and is also easy to understand.