Implementation of Binary Search Tree in C

Question

What is a Binary Seach Tree
A graph without any loop is called a tree which has exactly n-1 connectors/edges for n nodes and always have a unique path between any two nodes. If in this type of arrangement each node has two connection to child nodes and one to the parent node then it is called binary tree and if in this type of binary tree each left subnode is less then then parent node and rigt subnode is greater then parent then it is called binary seach tree.

See the following example -

Necessary Operations
Add Node
Delete Node
Search A Node
In Order Traversal
Post Order Traversal
Pre Order Traversal

Sample Code

struct node
{
    int data;
    struct node *lsubtree;
    struct node *rsubtree;
};

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->lsubtree = null;
    new->rsubtree = null;
    new->data = data;

    return new;
} 

void add_node(int data, struct node **head)
{
    if (*head == null)
    {
        *head = create_node(data);
    }
    else if (data < (*head)->data)
    {
        add_node(data, &(*head)->lsubtree);
    }
    else if (data > (*head)->data)
    {
        add_node(data, &(*head)->rsubtree);
    }
}

struct node * inorder_successor(struct node* node)
{
    struct node* current = node;

    // loop down to find the leftmost leaf
    while (current->lsubtree != NULL)
        current = current->lsubtree;

    return current;
}

struct node* delete_node(int data, struct node* root)
{
    struct node *temp;

    if (root == NULL) return root;

    if (data < root->data)
        root->lsubtree = delete_node(data, root->lsubtree);
    else if (data > root->data)
        root->rsubtree = delete_node(data, root->rsubtree);
    else
    {
        // This is the node to be deleted 

        // node with only one child or no child
        if (root->lsubtree == NULL)
        {
            temp = root->rsubtree;
            free(root);
            return temp;
        }
        else if (root->rsubtree == NULL)
        {
            temp = root->lsubtree;
            free(root);
            return temp;
        }

        // node with two children then get the inorder successor
        temp = inorder_successor(root->rsubtree);

        // Copy the inorder successor's content to this node
        root->data = temp->data;

        // Delete the inorder successor
        root->rsubtree = delete_node(temp->data, root->rsubtree);
    }

    return root;
}

struct node *search(int data, struct node *head)
{
    if (head != null)
    {
        if (data == head->data)
        {
            return head;
        }
        else if (data < head->data)
        {
            return search(data, head->lsubtree);
        }
        else
        {
            return search(data, head->rsubtree);
        }
    }
    else return null;
}

void preorder_traversal (struct node * root)
{
    if (root != NULL) {
        printf("%c ", root->data);
        preorder_traversal(root->lsubtree);
        preorder_traversal(root->rsubtree);
    }
}

void inorder_traversal (struct node * root)
{
    if (root != NULL) {
        inorder_traversal(root->lsubtree);
        printf("%c ", root->data);
        inorder_traversal(root->rsubtree);
    }
}

void postorder_traversal (struct node * root)
{
    if (root != NULL) {
        postorder_traversal(root->lsubtree);
        postorder_traversal(root->rsubtree);
        printf("%c ", root->data);
    }
}

Comments

First time we have seen BST with delete operation (hope it is tested code)