Binary search tree lookup output

Question

I am attempting to implement a lookup function for a binary search tree. While it does return true if I lookup the root of the tree, when I lookup other entries that are in the tree it returns false. When I debugged it the function seemed to return 1 but would then continue running and then return 0 at the end. It was my understanding that the function should terminate as soon as it returns any value so I'm not sure why this is happening.

int lookup(int n,struct node* x)
{
    if (x->data==n)
    {
        return 1;
    }
    else if (x->left==NULL && x->right==NULL)
    {
        return 0;
    }
    else if (n>x->data && x->right!=NULL)
    {
        lookup(n,x->right);
    }
    else
    {
        lookup(n,x->left);
    }
    return 0;
}

Answer 1

The function has incorrect behavior because it returns nothing in these if statements

    else if (n>x->data && x->right!=NULL)
    {
        lookup(n,x->right);
    }
    else
    {
        lookup(n,x->left);
    }

That is the control will be passed to the last return statement after the if-else statements

    return 0;

But if you will update the function like

int lookup(int n,struct node* x)
{
    if (x->data==n)
    {
        return 1;
    }
    else if (x->left==NULL && x->right==NULL)
    {
        return 0;
    }
    else if (n>x->data && x->right!=NULL)
    {
        return lookup(n,x->right);
    }
    else
    {
        return lookup(n,x->left);
    }
    return 0;
}

nevertheless the function can invoke undefined behavior because it does not check whether the pointer x is equal to NULL.

For example let's assume that x->data is not equal to n and n is less than x->data. Also let's assume that x->left is equal to NULL and x->right is not equal to NULL.

In this case the sub-statement of the first if statement

    if (x->data==n)
    {
        return 1;
    }

will not be executed.

And the sub-statement of the second if statement also will not be executed because x->right is not equal to NULL.

    else if (x->left==NULL && x->right==NULL)
    {
        return 0;
    }

The same problem will exists with the third if statement.

So the control will be passed inside the last else statement

    else
    {
        lookup(n,x->left);
    }

where the function is called with the null-pointer x->left. Thus in the second call of the function you will try to use the null-pointer to access memory

    if (x->data==n)
    {
        return 1;
    }

The function can be written the following way. Pay attention to that as the function does not change the tree itself its second parameter should be declared with the qualifier const.

int lookup( int n, const struct node *x )
{
    if ( x == NULL )
    {
        return 0;
    }
    else if ( n < x->data )
    {
        return( n, x->left );
    }
    else if ( x->data < n )
    {
        return ( n, x->right );
    }
    else
    {
        return 1;
    }
}

Also usually such a function is declared with the first parameter that specifies the pointer to the node (to the tree) and the second parameter specifies what is searched. That is like

int lookup( const struct node *x, int n );

Or even like

_Bool lookup( const struct node *x, int n );