A binary search tree works best when code is available to search the tree. Before doing so, I’d like to demonstrate how a tree is processed, one node at a time.

Continuing from last week’s Lesson, to visit each node in the tree you must traverse the tree, plumbing its depths. I call this function traverse():

/* traverse the tree */
void traverse(struct node *r)
{
    /* stop on NULL, empty node */
    if( r==NULL )
        return;

    /* fetch data */
    printf("%d\n",r->key);
    /* go deeper! */
    traverse(r->right);
    traverse(r->left);
}

As with the add_node() function, traverse() is recursive. When a NULL node is encountered, indicating an empty item, the function returns. Otherwise, it fetches a key value from the node and then traverses first the right branches and then the left branches in the tree. Eventually, all values are output, though in a manner that dominates the right branches (because the right node is inspected first).

Here’s sample output from the updated code, available on GitHub:

50
85
96
59
68
20
41
16
3

Compare this output with the way the data is stored internally, which is illustrated in Figure 1. You can see how the output favors climbing down the right branches first.

Figure 1. A Binary Search Tree.

If you change the order of the traverse() recursive call, putting the traverse(r->left) statement first, the output appears in a different order. Regardless, these functions are used more properly to search for data than to output an accurate representation of the tree.

The second improvement to the original code I promised is to free the allocated nodes before the program quits. As with all a program’s allocated storage, nodes are freed automatically when the program ends. Still, C coders are persnickety (as they should be) with regards to freeing memory.

To de-allocate the binary search tree’s storage, I added the free_tree() function to the sample code:

/* 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 */
}

As you may suspect, this function is also recursive. It seeks the bottom-most (top-most?) node in the tree and frees it, free(r). This function is added to the end of the main() function and is available on GitHub here.

The next task is to search the tree for a specific tidbit of data. I present this addition to the code in next week’s Lesson.