CODEWITHSUNDEEP
c
Wai Chin
Wai Chin

Reputation: 107

homework - Binary Search Tree C

I am stucked on this simple binary search tree very long as my main problem is that the (BST * bst) in function bst_get() is NULL.

typedef struct {
    char *key;
    void *value;
} KVP;
typedef struct bst {
    struct bst *left;
    struct bst *right;
    KVP kvp;
} BST;

This insert function get the arguments from an input file and would sort accordingly 

BST *bst_insert(BST *bst, char*key, void *value){
    if(bst==NULL){
        BST * tempBST = (BST * )malloc(sizeof(BST));
        //strcpy(tempBST->kvp.key , key);
        tempBST->kvp.key = key;
        tempBST->kvp.value = value;
        tempBST->left = NULL;
        tempBST->right = NULL;
        puts(key);
        return tempBST;
    }else
    //if(strcmp(key , bst->kvp.key) > 0){ // i tried to compare strings but it failed
    if(key > bst->kvp.key && bst != NULL){
        bst->right = bst_insert(bst->right , key , value);
        return bst;
    }
    else
    if(key < bst->kvp.key){
        bst->left = bst_insert(bst->left , key, value);
        return bst;
    }    
}

and when it's time to compare this BST with the key (from another file) as below

KVP *bst_get(BST *bst , char *key)

    if(bst!=NULL){
        if(key==bst->kvp.key){
            return &bst->kvp;
        }
        else if (key > bst->kvp.key) {
           return bst_get(bst->right , key);
        } else if (key < bst->kvp.key){
           return bst_get(bst->left , key);
        } 
    }else{
        printf("BST IS EMPTY!\n");
    }
}

the sentence "BST IS EMPTY" is printed. I have no idea what's going on with my BST as I referred to other similar questions and it seemed that I missed out some important issue here and would like to get some help regarding this.

Thank you for your time

Upvotes: 3

Views: 429

Answers (3)

Some programmer dude
Some programmer dude

Reputation: 409176

Of course you will get to the point of bst being NULL in bst_get, as you keep calling the function recursively with either the left or the right member. Sooner or later one of them are going to be NULL, leading to you printing the string.

If you used a debugger to step though the code and the recursive calls you would have noticed that.

Upvotes: 0

abelenky
abelenky

Reputation: 64682

I haven't gone over all the code, but this part stands out as wrong:

if(key > bst->kvp.key && bst != NULL)

Consider the scenario where bst is NULL, heading into this statement.

First, it will compare key to bst->kvp.key, which uses the bst pointer. And since bst is NULL, you just encountered a crashing bug. (likely a Segmentation Violation).

You need to reverse the order, so that bst is checked for NULL before you try to use the pointer:

if( (bst != NULL) && (key > bst->kvp.key) )

Further, based on your commented out code before this statement, I think you want to try:

if( (bst != NULL) && strcmp(key , bst->kvp.key) > 0) {

That should both protect against a NULL pointer, and use a string comparison instead of a pointer comparison.

Upvotes: 4

Oswald
Oswald

Reputation: 31647

In function bst_get(), key==bst->kvp.key compares pointers, not string content. Use strcmp to compare string content. Same goes for all the other places where you compare keys.

Upvotes: 1

Related Questions