C Binary Search Tree

Summary: this tutorial introduces you to binary search tree data structure and how to implement it in C.

Introduction to binary search tree

A binary search tree or BST is a binary tree in symmetric order.

A binary search tree can:

• Be empty
• Have a key and not more than two other subtrees, which are called left subtree and right subtree.

A binary search tree is in symmetric order, it means:

• Each node contains a key.
• Each node’s key is smaller than all node’s keys in the right subtree and bigger than all node’s keys in the left subtree.

A binary search tree is also known as sorted or ordered binary tree.

Binary search tree operations

There are some common operations on the binary search tree:

• Insert – inserts a new node into the tree
• Delete – removes an existing node from the tree
• Traverse – traverse the tree in pre-order, in-order and post-order. For the binary search tree, only in-order traversal makes sense
• Search – search for a given node’s key in the tree

All binary search tree operations are O(H), where H is the depth of the tree. The minimum height of a binary search tree is H = log₂N, where N is the number of the tree’s nodes. Therefore the complexity of a binary search tree operation in the best case is O(logN); and in the worst case, its complexity is O(N).

The worst case happens when the binary search tree is unbalanced. Many algorithms have been invented to keep a binary search tree balanced such as the height-balanced tree or AVL trees of Adelson-Velskii and Landis, B-trees, and Splay trees.

C binary search tree implementation

We can use a structure to model the binary search tree node a follows:

typedef struct node
{
    int data;
    struct node* left;
    struct node* right;
} node;
Code language: C++ (cpp)

The node structure has three members:

• data: stores node’s key, which is an integer. You can store a string, a pointer to a structure or (void*). For the sake of simplicity, we will use a binary search tree of integers.
• left: points to the left subtree.
• right: points to the right subtree.

To create a new node, we use the malloc() function to allocate memory dynamically as follows:

/*
    create a new node
*/
node* create_node(int data)
{
    node *new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        fprintf (stderr, "Out of memory!!! (create_node)\n");
        exit(1);
    }
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}
Code language: C++ (cpp)

To compare the data of two nodes, we can compare two integers. However, to make it more extensible, we can pass a callback to any function that has a comparison between two keys of nodes. The callback for comparing two nodes is defined as follows:

typedef int (*comparer)(int, int);
Code language: C++ (cpp)

Later on, you may change the type of data to string, float, or even void*, and change the comparer callback accordingly.

Insert a new node into the binary search tree

If the binary search tree is empty, we just create a new node, otherwise, we start from the root node:

We find the proper position for the new node by comparing the new node’s key with the root node’s key. If the key of the new node less than the root node’s key, we go to the left subtree. If the key of the new node is greater than the root node’s key, we go to the right subtree. We do this step recursively until we find the correct position in the tree to insert the new node.

The following illustrates the insert_node function:

/*
    insert a new node into the BST
*/
node* insert_node(node *root, comparer compare, int data)
{

    if(root == NULL)
    {
        root = create_node(data);
    }
    else
    {
        int is_left  = 0;
        int r        = 0;
        node* cursor = root;
        node* prev   = NULL;

        while(cursor != NULL)
        {
            r = compare(data,cursor->data);
            prev = cursor;
            if(r < 0)
            {
                is_left = 1;
                cursor = cursor->left;
            }
            else if(r > 0)
            {
                is_left = 0;
                cursor = cursor->right;
            }

        }
        if(is_left)
            prev->left = create_node(data);
        else
            prev->right = create_node(data);

    }
    return root;
}
Code language: C++ (cpp)

Delete a node from the binary search tree

Deleting an existing node in the binary search tree is little more complicated. There are three cases that we should consider:

Case 1. Delete a leaf node i.e., the node that has no children. We just need to remove it. The following example illustrates how to remove the leaf node e.g., 13

Case 2. Remove a node that has 1 child node, we replace it with its child node and remove it e.g., to remove node 10 in the following picture.

Case 3. To remove a node that has two child nodes or two children, we find its in-order successor node, which is the next node in an in-order traversal of the tree, and replaces it with the in-order success node.

For example, to remove the node 3, we find its in-order successor node, which is 4, and replace the node 3 by 4 as illustrated in the following picture.

The following is the delete node function that uses the recursive function in C:

/*
    delete a node in the binary search tree
*/
node* delete_node(node* root, int data,comparer compare)
{
    if(root == NULL)
        return NULL;

    node *cursor;
    int r = compare(data,root->data);
    if( r < 0)
        root->left = delete_node( root->left, data,compare);
    else if( r > 0 )
        root->right = delete_node(root->right,data,compare);
    else
    {
        if (root->left == NULL)
        {
            cursor = root->right;
            free(root);
            root = cursor;
        }
        else if (root->right == NULL)
        {
            cursor = root->left;
            free(root);
            root = cursor;
        }
        else    //2 children
        {
            cursor = root->right;
            node *parent = NULL;

            while(cursor->left != NULL)
            {
                parent = cursor;
                cursor = cursor->left;
            }
            root->data = cursor->data;
            if (parent != NULL)
                parent->left = delete_node(parent->left, parent->left->data,compare);
            else
                root->right = delete_node(root->right, root->right->data,compare);
        }
    }
    return root;
}
Code language: C++ (cpp)

Search for a specific key in the binary search tree

To search for a specific key in the binary search tree, we start from the root node. If the tree is empty, the key does not exist. Otherwise, if the root node’s key is equal to the key, the search is successful, we terminate the search. If the key is less than the root node’s key, we search the left subtree. Likewise, if the key is greater than the root node’s key, we search the right subtree. We repeat this step recursively until the key is found or subtree is NULL.

/*
    search for a specific key
*/
node* search(node *root,const int data,comparer compare)
{
    if(root == NULL)
        return NULL;

    int r;
    node* cursor = root;
    while(cursor != NULL)
    {
        r = compare(data,cursor->data);
        if(r < 0)
            cursor = cursor->left;
        else if(r > 0)
            cursor = cursor->right;
        else
            return cursor;
    }
    return cursor;

}
Code language: C++ (cpp)

Traverse the binary search tree

We can traverse the binary search tree once it is created by traversing recursively to the left subtree of the root node, accessing the root node’s data, and then recursively traversing to the right subtree of the root node. This is called in-order traversal of a binary tree.

Because of the rules of the nodes’ keys in the binary search tree, this in-order traversal always creates a sorted list of nodes.

The following is the in-order traversal function of the binary search tree:

/*
    in order traversal the binary search tree
*/
void traverse(node *root,callback cb)
{
    node *cursor, *pre;

    if(root == NULL)
        return;

    cursor = root;

    while(cursor != NULL)
    {
        if(cursor->left != NULL)
        {
            cb(cursor);
            cursor = cursor->right;
        }
        else
        {
            pre = cursor->left;

            while(pre->right != NULL && pre->right != cursor)
                pre = pre->right;

            if (pre->right != NULL)
            {
                pre->right = cursor;
                cursor = cursor->left;
            }
            else
            {
                pre->right = NULL;
                cb(cursor);
                cursor = cursor->right;
            }
        }
    }
}
Code language: C++ (cpp)

Notice that we pass a callback to the traverse function so that we can manipulate the node dynamically. The callback is defined as follows:

typedef void (*callback)(node*);
Code language: C++ (cpp)

Remove all nodes

We must deallocate memory allocated for all the nodes in the binary search tree. We can create a function named dispose() to do this:

/*
    recursively remove all nodes of the tree
*/
void dispose(node* root)
{
    if(root != NULL)
    {
        dispose(root->left);
        dispose(root->right);
        free(root);
    }
}
Code language: C++ (cpp)

C binary search tree program

Before creating a program to test our binary search tree, we need to create some functions for comparing two integers:

/*
    compare two integers
*/
int compare(int left,int right)
{
    if(left > right)
        return 1;
    if(left < right)
        return -1;
    return 0;
}
Code language: C++ (cpp)

Displaying a node:

/*
    display a node's key
*/
void display(node* nd)
{
    if(nd != NULL)
        printf("%d ",nd->data);
}
Code language: C++ (cpp)

And a function for displaying the whole tree:

/*
    Recursively display tree or subtree
*/
void display_tree(node* nd)
{
    if (nd == NULL)
        return;
    /* display node data */
    printf("%d",nd->data);
    if(nd->left != NULL)
        printf("(L:%d)",nd->left->data);
    if(nd->right != NULL)
        printf("(R:%d)",nd->right->data);
    printf("\n");

    display_tree(nd->left);
    display_tree(nd->right);
}
Code language: C++ (cpp)

Now it’s time to play with the binary search tree:

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

#include "bst.h"

#define SIZE 9

int main()
{
    node* root = NULL;
    comparer int_comp = compare;
    callback f = display;

    /* insert data into the tree */
    int a[SIZE] = {8,3,10,1,6,14,4,7,13};
    int i;
    printf("--- C Binary Search Tree ---- \n\n");
    printf("Insert: ");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ",a[i]);
        root = insert_node(root,int_comp,a[i]);
    }
    printf(" into the tree.\n\n");

    /* display the tree */
    display_tree(root);

    /* remove element */
    int r;
    do
    {
        printf("Enter data to remove, (-1 to exit):");
        scanf("%d",&r);
        if(r == -1)
            break;
        root = delete_node(root,r,int_comp);
        /* display the tree */
        if(root != NULL)
            display_tree(root);
        else
            break;
    }
    while(root != NULL);

    /* search for a node */
    int key = 0;
    node *s;
    while(key != -1)
    {
        printf("Enter data to search (-1 to exit):");
        scanf("%d",&key);

        s = search(root,key,int_comp);
        if(s != NULL)
        {
            printf("Found it %d",s->data);
            if(s->left != NULL)
                printf("(L: %d)",s->left->data);
            if(s->right != NULL)
                printf("(R: %d)",s->right->data);
            printf("\n");
        }
        else
        {
            printf("node %d not found\n",key);
        }
    }

    /* remove the whole tree */
    dispose(root);
    return 0;
}
Code language: C++ (cpp)

The following is the output of the binary search tree program in C:

--- C Binary Search Tree ----

Insert: 8 3 10 1 6 14 4 7 13  into the tree.

8(L:3)(R:10)
3(L:1)(R:6)
1
6(L:4)(R:7)
4
7
10(R:14)
14(L:13)
13
Enter data to remove, (-1 to exit):13
8(L:3)(R:10)
3(L:1)(R:6)
1
6(L:4)(R:7)
4
7
10(R:14)
14
Enter data to remove, (-1 to exit):10
8(L:3)(R:14)
3(L:1)(R:6)
1
6(L:4)(R:7)
4
7
14
Enter data to remove, (-1 to exit):3
8(L:4)(R:14)
4(L:1)(R:6)
1
6(R:7)
7
14
Enter data to remove, (-1 to exit):-1
Enter data to search (-1 to exit):6
Found it 6(R: 7)
Enter data to search (-1 to exit):13
node 13 not found
Enter data to search (-1 to exit):-1
node -1 not found
Code language: CSS (css)

In this tutorial, you have learned how to implement the binary search tree in C.