Abstract Binary Search Tree Implementation in C

There are several ways to store data using different data structures like Array, Linked Lists , Trees, Graphs, Hashmaps etc. The choice of the data structure depends on the application which extracts that data. On searching the web , one can easily find out which data structure is required for their application. Binary Search Tree is one such data structure which is generally used for storing data.

A binary search tree consists of members called as nodes which have the data embedded in them. Generally, a BST node contains address fields and data field. The structure of a BST is something like this :

Each node can have a left subtree and right subtree which may or may not have any nodes.

Binary Search tree has some properties which identifies it :

• The left subtree members have a value which is always less than the value at the root node
• The right subtree members have a value which is always greater than the value at the root node
• Both the subtrees must be also a BST.

The implementation provided in this post uses an abstract data type (void). To use this implementation as it is, one must implement these two functions 

1. Comparison Function - This function compares the data between two nodes. This function must return -1, 0 or 1 only.  The signature for this function is int <function-name> (void * data1, void * data2).
1. Function should return 1 when data1 is greater than data2.
2. Function should return -1 when data1 is lesser than data2.  
3. Function should return 0 when data1 is equal to data2.  
2. Display Function - This function is used for display purposes only. It displays the node data.

A sample implementation of these two functions is presented in the driver example(bstdriver.c) for the BST. This sample implementation uses int type as data.

 
/*bst.h*/
typedef struct bstNode
{
    struct bstNode *left;       /*Left Child*/
    struct bstNode *right;      /*Right Child*/
    struct bstNode *parent;     /*Parent Child*/
    void *data;                 /*Data*/
}BSTNode;

void BSTDestroy(BSTNode *root);
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *));
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *));

 
/*bst.c*/
#include <stdio.h>
#include <stdlib.h>

#include "bst.h"

/* @brief Function to determine if a child is a left child or right child in a BST
 * @param data Pointer to the data to be used
 * @return LEFT - if left child
 *         RIGHT - if right child
 */
static inline const char* BSTFindChildLoc(BSTNode *parent, BSTNode *child)
{
    return (((parent->left)==(child))?"LEFT":"RIGHT");
}

/* @brief Function to swap data between two nodes in a BST
 * @param data Pointer to the data to be used
 * @return void
 */
static inline void BSTSwapNodeData(BSTNode **node1, BSTNode **node2 )
{
    void *tmp;
    tmp = (*node1)->data;
    (*node1)->data = (*node2)->data;
    (*node2)->data = tmp;
}

/* @brief Function to create a node in a BST
 * @param data Pointer to the data to be used
 * @return Address of the node created
 */
BSTNode* BSTCreateNode(void *data)
{
    /*Allocate memory*/
    BSTNode* node= (BSTNode*)malloc(sizeof(BSTNode));

    if(NULL == node)
    {
        printf("Error: Memory Allocation could not be completed\n");
        return NULL;
    }

    /*Initialize links*/
    node->left = NULL;
    node->right= NULL;
    node->parent= NULL;
    node->data = data;

    printf("Allocated Node with address %p\n", node);
    return node;
}

/* @brief Function to destroy all nodes in a BST
 * @param root Pointer to the root of the BST
 * @return void
 */
void BSTDestroy(BSTNode *root)
{
    if(root)
    {
        /*Traverse down the left subtree*/
        if(root->left)
            BSTDestroy(root->left);
        /*Traverse down the right subtree*/
        if(root->right)
            BSTDestroy(root->right);
        /*Free the memory*/
        free(root);
        printf("DeAllocated Node with address %p\n", root);
    }
}

/* @brief Function to insert a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be inserted
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *tmp = NULL;
    BSTNode *ptr = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }


    if(!(*root))
    {
        /*Create a node*/
        tmp = BSTCreateNode(data);

        if(NULL == tmp)
        {
            printf("Error: Node insertion failed\n");
            return;
        }

        /*Root Node*/
        *root = tmp;
        return;
    }

    ptr = *root;

    /*If data is greater than the current node's data*/
    if(cmp_fn(data,ptr->data) == 1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->right == NULL)
        {
            /*Create a node*/
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->right = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->right), data, cmp_fn);
        }
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data,ptr->data) == -1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->left == NULL)
        {
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->left = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->left), data, cmp_fn);
        }
    }
    /*If data is equal to the current node's data*/
    else
        printf("Error: Duplicate\n");
}

/* @brief Function to find the minimum valued node in the left subtree of a node
 * @param node Pointer to the node whose min valued child in left subtree has to be found
 * @return Address of the minimum valued node in the left subtree
 */
static BSTNode* BSTMinVal(BSTNode* node)
{
    BSTNode* current = node;

  /*Go to the leftmost member of the tree */
  while (current->left != NULL)
  {
    current = current->left;
  }
  return current;
}

/* @brief Function to find the Inorder successor of a node in a BST
 * @param node Pointer to the node whose inorder successor has to be found
 * @return Address of the Inorder successor
 */
static BSTNode* BSTInorderSuccessor(BSTNode* node)
{
    BSTNode *inOrdSucc = NULL;
    if(NULL == node)
        return NULL;

    /*Traverse the right subtree and find the minimum value */
    if( node->right != NULL )
        return BSTMinVal(node->right);

    inOrdSucc = node->parent;

    while(inOrdSucc != NULL && node == inOrdSucc->right)
    {
        node = inOrdSucc;
        inOrdSucc = inOrdSucc->parent;
    }
    return inOrdSucc;

}

/* @brief Helper Function to update the parent node links in a BST
 * @param node Pointer to pointer to the node whose parent will be updated
 * @param ptr Target Link
 * @return void
 */
static inline void updateParent(BSTNode **node, BSTNode *ptr)
{
    /*If the child is a left child*/
    if(BSTFindChildLoc((*node)->parent, *node) == "LEFT")
    {
        (*node)->parent->left = ptr;
    }
    /*If the child is a right child*/
    else
    {
        (*node)->parent->right = ptr;
    }
}

/* @brief Function to delete a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;
    BSTNode *tmp = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }

    /*Search if the node exists in the BST*/
    ptr = BSTSearch(*root, data, cmp_fn);

    if(NULL == ptr)
    {
        printf("Error: Node not found\n");
        return;
    }

    /*If the node has no children*/
    if(ptr->left == NULL && ptr->right == NULL)
    {
        /*No children*/
         tmp = ptr;

         /*Non-Root Node*/
         if(ptr->parent)
            updateParent(&ptr, NULL);   /*Update the parent's link*/
         /*Root Node*/
         else
             *root = NULL;

         ptr = NULL;
         free(tmp);
         printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has single child*/
    else if((ptr->left != NULL && ptr->right == NULL) || (ptr->left == NULL && ptr->right != NULL))
    {
        tmp = ptr;

        /*Single Child*/
        if((ptr->left != NULL) && (ptr->right == NULL))
        {
            ptr->left->parent = ptr->parent;

            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->left);   /*Update the parent's link*/
            /*Root Node*/
            else
                *root = ptr->left;
        }
        else
        {
            ptr->right->parent = ptr->parent;   /*Update the parent's link*/
            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->right);
            /*Root Node*/
            else
                *root = ptr->right;
        }

        free(tmp);
        printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has two children*/
    else if((ptr->left != NULL) && (ptr->right != NULL))
    {
        /*Find the inorder successor of the node*/
        BSTNode *inOrdSucc = BSTInorderSuccessor(ptr);

        /*Swap the node's data with inorder successor's data*/
        BSTSwapNodeData(&ptr, &inOrdSucc);

        /*Delete the inorder successor node*/
        BSTDelete(&inOrdSucc, data, cmp_fn);
    }
}

/* @brief Function to search a data in a BST
 * @param root Pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return Address of the node found
 *         NULL if node not found
 */
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;

    if(NULL == root)
        return NULL;

    ptr = root;

    /*If the data is found*/
    if(cmp_fn(data, ptr->data) == 0)
    {
        return ptr;
    }
    /*If data is greater than the current node's data*/
    else if(cmp_fn(data, ptr->data) == 1)
    {
        return BSTSearch(ptr->right, data, cmp_fn);
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data, ptr->data) == -1)
    {
        return BSTSearch(ptr->left, data, cmp_fn);
    }

    return NULL;
}

/* @brief Function to traverse all nodes in a BST in InOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTInOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTInOrder(root->left, display_fn);

    printf("[%p]",root->data);
    display_fn(root);

    if(root->right)
        BSTInOrder(root->right, display_fn);

}

/* @brief Function to traverse all nodes in a BST in PostOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPostOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTPostOrder(root->left, display_fn);

    if(root->right)
        BSTPostOrder(root->right, display_fn);

    printf("[%p]",root->data);
    display_fn(root);
}

/* @brief Function to traverse all nodes in a BST in PreOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPreOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    printf("[%p]",root->data);
    display_fn(root);

    if(root->left)
        BSTPreOrder(root->left, display_fn);

    if(root->right)
        BSTPreOrder(root->right, display_fn);

}

/* @brief Function to display all nodes in a BST
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *))
{
    printf("InOrder ->",root->data);
    BSTInOrder(root,display_fn);
    printf("\n",root->data);

    printf("PreOrder ->",root->data);
    BSTPreOrder(root,display_fn);
    printf("\n",root->data);

    printf("PostOrder ->",root->data);
    BSTPostOrder(root,display_fn);
    printf("\n",root->data);
}

 
/*bstdriver.c*/
/*
 * Compile: gcc -o test bst.c bstdriver.c
 * Run: ./test
 */
#include <stdio.h>
#include "bst.h"

int data[]={9,1,6,3,8,4,2,5,7};

/*Comparison function*/
int cmp_fn(void *data1, void *data2)
{
    if(*((int*)data1) > *((int*)data2))
        return 1;
    else if(*((int*)data1) < *((int*)data2))
        return -1;
    else
        return 0;
}

/*Display Function*/
static void displayNode(BSTNode *node)
{
    if(node)
        printf("%d ",*((int*)node->data));
}

int main()
{
    BSTNode *root = NULL;

    int i,sVal=-1;
    int size = sizeof(data)/sizeof(data[0]);

    for(i=0; i < size; i++)
        BSTInsert(&root, &data[i], cmp_fn);

    BSTDisplay(root, displayNode);

    printf("Search Value : ");
    scanf("%d", &sVal);

    if(NULL == BSTSearch(root, &sVal, cmp_fn))
        printf("Not Found\n");
    else
        printf("Found\n");

    printf("Delete Value : ");
    scanf("%d", &sVal);
    BSTDelete(&root, &sVal, cmp_fn);
    BSTDisplay(root, displayNode);

    BSTDestroy(root);
}