Binary Search Tree does not recognize values properly

Question

I am trying to implement a Binary Serach Tree using C. Here in this code I added few values to the tree and then trying to check whether that values is in the tree. But my attempted code always return true.

I have checked many times. I am still learning C programming.

Here is my code.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct BSTnode {
    int data;
    struct BSTnode *left;
    struct BSTnode *right;
    } BSTnode;

BSTnode *getNewNode(int data){
    BSTnode *newNode = (BSTnode*)malloc(sizeof(BSTnode));
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    }
BSTnode* InsertNew(BSTnode *root,int data){
    if(root == NULL){
        root = getNewNode(data);
                }
        else if(data <= root->data){
            root->left = InsertNew(root->left,data);
            } else{
                root->right = InsertNew(root->right,data);
                }
        return root;
        }

bool search(BSTnode *root, int data){
    if(root== NULL) return false;
    else if(root->data == data) return true;
    else if (data <= root->data) return search(root->left,data);
    else return search(root->right,data);

    }
int main()
{
//node to store root

BSTnode *root = NULL;

root = InsertNew(root,34);
root = InsertNew(root,4);
root = InsertNew(root,3);
root = InsertNew(root,1);

int num;
printf("enter a number : \n");
num =scanf("%d");

if(search(root,num)==true){
    printf("found");
    }else{
    printf("not found");
    }
    return 0;
}

What am I missing here?

Thanks in advance.

Answer 1

You are missing that

num =scanf("%d");

doesn't do what you think it does (scanf returns the number of items successfully converted or -1 on EOF). You didn't crank your compiler's warning level high enough to tell you that you need

if (scanf ("%d", &num) != 1) {
    /* complain */
}

In your broken program, scanf() happens to return 1 (because it converted 1 item and wrote it to random memory) and since there's a 1 in the tree, you always get true.

Answer 2

For starters according to the C Standard the function main without parameters shall be declared like

int main( void )

The function getNewNode

BSTnode *getNewNode(int data){
    BSTnode *newNode = (BSTnode*)malloc(sizeof(BSTnode));
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    }

has undefined behavior because it returns nothing though has the return type BSTnode *.

The function can be defined the following way

BSTnode * getNewNode( int data )
{
    BSTnode *newNode = ( BSTnode * )malloc( sizeof( BSTnode ) );

    if ( newNode != NULL )
    {
        newNode->data = data;
        newNode->left = newNode->right = NULL;
    }

    return newNode;
}

The function InsertNew is wrong.Take into account that for binary search tree there is usually used the operator < instead of the operator <=.

These statements

root->left = InsertNew(root->left,data);

and

root->right = InsertNew(root->right,data); 

do not make sense and overwrites the values of root->left and root->right of nodes that shall not be actually changed. Also the created node can be equal to NULL and in this case the original root node will be also overwritten by NULL.

It is better to pass the original root node by reference through pointer.

Also you should use operator < instead of the operator <=.

The function definition can look the following way

BSTnode * InsertNew( BSTnode **root,int data )
{
    if ( *root == NULL )
    {
        *root = getNewNode( data );
        return *root;
    }
    else if ( data < ( *root )->data )
    {
        return InsertNew( &( *root->left ), data );
    } 
    else
    {
        return InsertNew( &( *root->right ), data );
    }
}

and the function can be called like

InsertNew( &root, 34 );

without assigning the return pointer to the root node. The return value can be checked in an if statement if it is needed.

If you do not want to have duplicate values in the tree then the function can be written the following way

BSTnode * InsertNew( BSTnode **root,int data )
{
    if ( *root == NULL )
    {
        *root = getNewNode( data );
        return *root;
    }
    else if ( data < ( *root )->data )
    {
        return InsertNew( &( *root->left ), data );
    } 
    else if ( ( *root )->data < data )
    {
        return InsertNew( &( *root->right ), data );
    }
    else
    {
        return NULL;
    }
}

Correspondingly the function search should be defined like

bool search( BSTnode *root, int data )
{
    if ( root == NULL ) 
    {
        return false;
    }
    else if ( data < root->data ) 
    {
        return search( root->left, data );
    }
    else if ( root->data < data )
    {
        return search( root->right, data );
    }
    else
    {
        return true;
    }
}

The using of the function scanf in this statement

num =scanf("%d");

is wrong.

The correct call will look like

printf( "enter a number : " );
scanf( "%d", &num );

You can also check whether the call was successful by using the condition in an if statement

if ( scanf( "%d", &num ) == 1 )
{
    //...
}

And you should free all allocated memory for the tree before exiting the program.

In general it is better to use the following condition

if(search(root,num) ){

instead of the strict comparison with true

if(search(root,num)==true){

because if the function will be rewritten such a way that in the case of success it will return any non-zero value then the strict comparison with true will not work.

Answer 3

In addition to the error pointed out by @Jens you are not returning a value from getNewNode. Add a statement:

return newNode;

at the end of that function. Here is a fixed example on ideone