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.

If you haven't yet, then this is the perfect time to learn how to use a debugger and how to use it (and other techniques) to debug your program. I suggest you take some time to read How to debug small programs by Eric Lippert. — Some programmer dude
– Some programmer dude, Commented Oct 18, 2017 at 11:08
And also compile with warnings on. For example, you don't return anything from getNewNode, when you should return the new node. — M Oehm
– M Oehm, Commented Oct 18, 2017 at 11:09
Try to work on fixing the indentation of your code - this will help both you and the future reader of your code. — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Oct 18, 2017 at 11:20

Jens · Accepted Answer · 2017-10-18 12:22:02Z

5

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.

edited Oct 18, 2017 at 12:22

answered Oct 18, 2017 at 11:10

Jens

73.3k16 gold badges134 silver badges186 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ivaylo Strandjev · Accepted Answer · 2017-10-18 11:15:57Z

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

answered Oct 18, 2017 at 11:15

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

2 Comments

Sachith Muhandiram Over a year ago

Please add scanf("%d",&num); to your answer. Because it was also a problem after fixing return newNode;

Ivaylo Strandjev Over a year ago

I have started my answer with In addition to the error pointed out by @Jens and I realize this is a problem, but that error was not spotted by me. Jens' answer gives enough detail on that and I don't see value in duplicating his explanation in my answer

Vlad from Moscow · Accepted Answer · 2017-10-18 12:06:36Z

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.

Collectives™ on Stack Overflow

Binary Search Tree does not recognize values properly

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related