Search Function in Binary Search Tree causes seg fault

Question

I've been trying to get this BST working for the last few days, and I am getting stuck on the search function. The logic seems to be correct (unless I'm missing very important details) but there still is something wrong with the code. Could it be because I am dealing with strings? Anyways, here is some code:

EDIT: I've pinpointed somewhere that seems to be going wrong. It turns out that my root is always null. I placed a printf to test if the NULL-case were true, and it always printed true. I've added my tree initialization at the bottom of this question.

The (Updated) Search Function:

//Thank you, M Oehm
node* search(node * tree, char *key)
{
    /* char *key is user input */
    int cmp;

    if(tree == NULL) {
        return NULL;
    }

    cmp = strcmp(key, tree->key);   
    if(cmp < 0) return search(tree->left, key);   
    if(cmp > 0) return search(tree->right, key);
    return tree;
}

Implementation in main function:

printf("Enter a string to search the tree with: ");
fgets(findNode, MAX_WORD, stdin);
findString = malloc(sizeof(char)*strlen(findNode)+1);
strcpy(findString,findNode);
printf("findString: %s\n", findString);
searched = search(&root, findString);
if(searched == NULL) {
    printf("No_such_key\n");
    free(findString);
    }
else {
    printNode(searched);
    free(findString);
    }
break;

Tree Initialization (via file parsing):

 /* Loop through each line in the file*/
 while(fgets(buffer, sizeof(buffer), file) != NULL) {
     tempToken = strtok(buffer, " \n");
     while(tempToken != NULL) {
         /* Assign default values */
         curr = (node *)malloc(sizeof(node));
         curr->left = curr->right = NULL;
         curr->key = malloc(sizeof(char)*strlen(tempToken)+1); /* +1 for '\0' */
         strcpy(curr->key, tempToken);
         curr->frequency = 1;           
         /* Insert node into tree */
         insert(&root, curr);
         /* Get next token */
         tempToken = strtok(NULL, " \n");
     }
 }
 /* Test insertion worked; close file */
 print_inorder(root);
 fclose(file);

Insertion Function:

void insert(node ** tree, node * item)
{
    /* If no root, item is root */
    if(!(*tree)) {
        *tree = item;
        return;
    }
    /* If item value is less than node in tree, assign to left */
    if(strcmp(item->key,(*tree)->key) < 0) {
        insert(&(*tree)->left, item);
    }
    else if(strcmp(item->key,(*tree)->key) > 0) {
        insert(&(*tree)->right, item);
    }
    else if(strcmp(item->key,(*tree)->key) == 0) {
        (*tree)->frequency++;
    }
}

The print function shows me that the insertion works properly.

Answer 1

Try changing your function to something like this.

node* search(node * tree, char * key)
{
    if(tree == NULL) {
        return NULL;
    }

    if(strcmp(key,tree->key) < 0) {
        return search(tree->left, key);
    }

    else if(strcmp(key,tree->key) > 0) {
        return search(tree->right, key);
    }


    printf("Success!\n");
    return tree;

}

A simple node* would suffice for your problem. No need for double pointers.

Answer 2

There are two errors in your code: You don't check whetehr the root node, to which you pass a pointer, is null and you don't return the results from the recursive functions.

Your function doesn't modify the tree, so you don't have to pass a pointer to the nodes. That method is useful for functions that modify the tree, e.g. for inserting or deleting nodes. Your function shoul pass a pointer to the root node. That also signals to the user that the tree won't be modified.

So here's a corrected version:

node* search(node *tree, const char *key)
{
    int cmp;

    if (tree == NULL) return NULL;

    cmp = strcmp(key, tree->key);

    if (cmp < 0) return search(tree->left, key);
    if (cmp > 0) return search(tree->right, key);
    return tree;
}

That version must be called like this:

node *hit = search(tree, "bingo!");

Note that this function does the string comparison only once and saves the result in a temporary variable. Your code calls strcmp up to three times.

You don't have to use recursion here. It's even a bit wasteful, because you have to percolate the answer up the first call. Recursion is useful when each step has to maintain a state, which you can represent as local variables. Here, you just change the input node.

Here's a non-recursive variant of the search function:

node* search(node *tree, const char *key)
{
    while (tree) {
        int cmp = strcmp(key, tree->key);

        if (cmp == 0) return tree;
        tree = (cmp < 0) ? tree->left : tree->right;
    }
    return NULL;
}

Answer 3

search(&(*tree)->left, key);

Should be:

return search(&(*tree)->left, key);

Same for the right case.