Binary Search Tree insertion Code UNEXPECTED behavior-CodePudding

I am inserting a node to the Binary Search Tree and I encountered an unexpected behaviour.

My question is - Why last line in insert function is optional ? The last line takes care of the recursive case, and it should be mandatory but when I run without the last line then also it works.

It works means, It successfully insert a node to BST.

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

struct node {
    int data;
    struct node *left;
    struct node *right;

};

typedef struct node Node;


struct node *insert(Node *root, int val)
{

    if(root == NULL){
   
        struct node *root = malloc(sizeof(struct node));
        root->data   = val;
        root->left  = root->right = NULL;
        return root;
    }
   
    if(root->data < val)
        root->right = insert(root->right,val);
   
    else if(root->data > val)
        root->left = insert(root->left,val);
    
    //return root; //WHY THIS LINE IS OPTIONAL
}

int main(){
    
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 5);
    root = insert(root, 1);
}

CodePudding user response：

The last line in insert() is very much optional but only if you're willing to put up with undefined behaviour. In your particular case, the UB seems to work correctly and that is certainly one possibility of UB.

In fact, it's one of its more insidious features since seeming correct behaviour may see your buggy code being released to you poor unsuspecting users :-)

As an example, with the stack going up and down due to function calls, it may just be that the previous value of root is returned because you're not loading a new value in to it. And, if the new value is the same as the previous one already on the stack, it may well seem to work.

However, the fact that it works in one specific case does not make it a good idea to rely on it.

Further expanding on the arbitrary values, consider this code:

#include<stdio.h>

int get42(void) { return 42; }
int getX(void) {}

int main(){
    int x = get42();
    //printf("123456789\n");
    int y = getX();
    printf("%d\n", x);
    printf("%d\n", y);
}

Keeping in mind this is UB so may act differently for you, this produces for me:

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
42
42

So despite the warning, it seems to give the same value as the previous function call. You can validate this by uncommenting the printf() and seeing:

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
123456789
42
10

The 10 there is the return value from the printf call (it returns the number of characters printed, nine digits and \n).

So, in this case, it very much seems that skipping a return statement will just allow the caller to pick up whatever was on the stack from a previous call (or some arbitrary value if this is the first call at that depth), such as with:

#include<stdio.h>

int get42(void) { return 42; }
int getX(void) {}

int main(){
    int x = 42;//get42();
    //printf("123456789\n");
    int y = getX();
    printf("%d\n", x);
    printf("%d\n", y);
}

producing for me:

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
42
-1539029341

But, as previously indicated, don't rely on this. The behaviour may change when you switch to a new compiler, a new compiler version, a new machine, or even decide to compile it on s Saturday instead of a weekday :-)