As you might suspect, searching a binary search tree (BST) involves a recursive function. This function must plow through the tree, finding a value in a specific node. Because the BST is organized, the search process works far more quickly than when the data is unorganized or set in a sequential array. In fact, the bsearch() function uses a similar scheme requiring that the data first be sorted before the function works its magic.

Continuing from last week’s Lesson, I’ve replaced the traverse() function with a search() function. Its arguments are a node pointer and the value to look for:

/* search for a value */
struct node *search(struct node *r, int v)
{
    /* return on empty or when key found */
    if( r==NULL || r->key == v )
        return(r);

    /* search for values less */
    if( v < r->key )
        return( search( r->left,v ) );
    /* search for values greater */
    return( search(r->right,v ) );
}

The first if test is for both the NULL pointer and the proper value. When the NULL pointer is encountered, the search has reached the end of a branch (or whatever the proper term is). When the key value is found, the search is over. At either point, recursion unwinds, returning the value of either NULL (failure) or the desired node (success).

The second if test plumbs the left node when the search value is less than the current node’s key value. The search is performed within the return statement, which is how the proper result — NULL or the found node — is returned to the calling statement.

When the value of the current node is greater than the current’s node’s key value, the search goes to the right node. The result is returned directly (that recursion thing).

The calling statement examines the returned result, either NULL for a failed search or the address of the node containing the matching key value.

Here is the full code:

2025_06_14-Lesson.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node {
    int key;
    struct node *left;
    struct node *right;
};

/* search for a value */
struct node *search(struct node *r, int v)
{
    /* return on empty or when key found */
    if( r==NULL || r->key == v )
        return(r);

    /* search for values less */
    if( v < r->key )
        return( search( r->left,v ) );
    /* search for values greater */
    return( search(r->right,v ) );
}

/* free the tree's node storage */
void free_tree(struct node *r)
{
    /* stop on NULL */
    if( r==NULL )
        return;

    /* plumb the depths */
    free_tree(r->left);
    free_tree(r->right);
    free(r);        /* the (current) bottom node */
}

/* add a new node */
struct node *add_node(struct node *r,int k)
{

    if( r==NULL )
    /* allocate a new node */
    {
        r = malloc( sizeof(struct node) );
        if( r==NULL )
        {
            fprintf(stderr,"Unable to allocate memory\n");
            exit(1);
        }
        r->key = k;        /* set its key */
        r->right = NULL;
        r->left = NULL;
    }
    else
    {
        /* smaller values go on the left */
        if( k < r->key )
            r->left = add_node(r->left,k);
        /* larger values go on the right */
        else
            r->right = add_node(r->right,k);
    }
    return(r);
}

int main()
{
    static int count = 9;
    int data[] = {
        50, 20, 85, 16, 41, 59, 96, 3, 68
    };
    struct node *root = NULL;
    struct node *result;
    int x,value;

    /* construct the tree */
    for( x=0; x<count; x++ )
        root = add_node(root,data[x]);

    /* search the tree */
    printf("Locate value: ");
    scanf("%d",&value);
    result = search(root,value);
    if( result!=NULL )
        printf("Value %d found\n",value);
    else
        printf("Value %d not found\n",value);

    /* clean-up */
    free_tree(root);
    return 0;
}

Obviously, more can be done with a Binary Search Tree beyond looking up simple values. The hurdle to clear from demonstration purposes is loading the tree with values.

For example, I could set all kinds of interesting data to search, but with the data already written in the code it seems silly to then search for what’s already known. Even so, binary search trees represent an excellent way to organize and locate data. You find this type of structure implemented often in programming, which is why being familiar with its operation and coding is important to know.