Tree structures are yet another way to organize data. They’re similar to a linked list, but with the data organized by value into a series of branches and leaves. OMG! It’s like a tree!

I’m not going to get into all the tree structure nomenclature as it’s confusing and often conflicting. For this series, I’m focusing on a specific type of tree, the Binary Search Tree or BST.

The BST is binary because each node has two child nodes. Other trees can have multiple child nodes, but for a BST the two nodes represent values: The left child node’s value is less than the root’s value, and the right child node’s value is greater. This organization cascades down, as illustrated in Figure 1.

Figure 1. A Binary Search Tree.

In Figure 1, the root value holds 50. It’s child values are 20 (less than, on the left) and 85 (greater than, on the right). This pattern continues, with values presented properly left and right.

The advantage of this structure is that it helps to quickly locate data. Finding a specific value involves traversing the tree in fewer steps than when the data is unorganized or presented sequentially.

To code a binary search tree, you need two major pieces: a structure and a function.

Here is a simple structure:

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

The node needs a value, supplied by integer variable key. Two child node members are left and right, both pointers. These pointers are set to NULL unless they also hold values.

The second thing needed is a function to add a new node. It’s not just any function, but a recursive function, which is designed to climb (or descend?) the tree looking for the proper node into which a value is plugged. Here is the function I’ve concocted:

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

The add_node() function requires a node structure pointer and integer value as its arguments. The function returns a node structure pointer.

The if-else decision in the structure handles two possibilities.

The initial if decision determines whether the address passed is initialized. If not (when it’s NULL), a new node is allocated. The value is assigned (variable k), and its two child nodes are initialized to NULL. Job done.

The else condition handles existing nodes. When the key value passed (argument k) is smaller than the current node’s key value, a new node is added on the left. Otherwise, the new node is added on the right. These additions are made recursively, so the function traverses the binary tree until it finds the proper spot for the key data.

The main() function contains a sample data set (appearing in Figure 1). It uses a for loop to build the tree, outputting the values as they’re added:

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

    /* construct the tree */
    for( x=0; x<count; x++ )
    {
        root = add_node(root,data[x]);
        printf("Added %d\n",data[x]);
    }

    return 0;
}

Here’s a sample run:

Added 50
Added 20
Added 85
Added 16
Added 41
Added 59
Added 96
Added 3
Added 68

You can view the entire code on GitHub here.

This code is just a start. Obviously, you must do more with the data than just store it. The code could also use improvement, in that duplicate values are added when they should be skipped (at least in this example).

Another big issue, especially with university students, is that none of these nodes are freed before the program ends. This process can be handled by traversing the tree, a topic I cover in next week’s Lesson.