C Binary Search Tree pre-order traversal with recursion

Question

I am working on a function that searches through a binary search tree in C for a name that is passed in with the function. However, I am stuck on how to format my loop so that the recusion doesn't simply end when the traversal reaches the left-most node with no children. The traversal has to be pre-order (visit myself, then my left child, then my right child).

My find function is as follows:

tnode *bst_find_by_name(tnode *ptr, const char *nom){

    if(ptr != NULL){
        if(strcmp(ptr->name, nom) == 0){
            return ptr;
        }
        if(ptr->left != NULL){
            return bst_find_by_name(ptr->left, nom);
        }
        if(ptr->right != NULL){
            return bst_find_by_name(ptr->right, nom);
        }
    }

    return NULL;


}

As you can see, currently this simply returns NULL once it reaches the left-most node that does not match the string that was passed into the function. I have to have it return NULL if it does not find a match in the tree, but at the same time I do not want it to return NULL too early before it has a chance to search every node in the tree. Any ideas?

Answer 1

Create a temporary variable that holds the return value. And check to see if bst_find_by_name returned something other than NULL if it returned NULL continue checking the tree.

Something like the following.

tnode *ret = NULL;
if(ptr->left != NULL){
    ret = bst_find_by_name(ptr->left, nom);
}
if(ret == NULL && ptr->right != NULL){
    ret = bst_find_by_name(ptr->right, nom);
}
return ret;

Answer 2

I prefer to write it like this:

tnode *bst_find_by_name(tnode *ptr, const char *nom) {
    // accept a null node, just exit early before dereferencing it
    if (ptr == NULL) {
        return NULL;
    }

    // is it this node?
    if(strcmp(ptr->name, nom) == 0){
        return ptr;
    }

    // remember, if the first part is true, || will skip the second part
    return bst_find_by_name(ptr->left, nom) || bst_find_by_name(ptr->right, nom)
}

Answer 3

// get the matching pointer for left or right subtree, and return 

tnode *bst_find_by_name(tnode *ptr, const char *nom) {
    // accept a null node, just exit early before dereferencing it
    if (ptr == NULL) {
        return NULL;
    }

    // is it this node?
    if(strcmp(ptr->name, nom) == 0){
        return ptr;
    }

    tnode * ptrtemp = bst_find_by_name(ptr->left, nom);
    if(!ptrtemp) {
        ptrtemp = bst_find_by_name(ptr->right, nom);
    } 
    return  ptrtemp;
}