C Program to Implement a Binary Search Tree (BST)

C Program to Implement a Binary Search Tree (BST)

By /

A Binary Search Tree (BST) is a special type of binary tree where each node follows a strict ordering property: the left child contains values less than the parent node, and the right child contains values greater than the parent node. BSTs allow efficient searching, insertion, and deletion operations, making them fundamental in algorithms requiring sorted data access.

Understanding the Problem

In a BST, maintaining the ordering property is crucial during insertion and deletion. Searching becomes faster compared to a regular binary tree because you can eliminate half of the tree at each step. Implementing a BST requires careful handling of pointers to ensure the tree structure remains valid after every operation.

Program 1: Insertion and Inorder Traversal

This program demonstrates how to create a BST by inserting nodes and performing an inorder traversal to display the tree in sorted order.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Inorder traversal (Left, Root, Right)
void inorder(Node *root) {

    if (root == NULL) return;

    inorder(root->left);

    printf("%d ", root->data);

    inorder(root->right);

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal of BST: ");
    inorder(root);
    printf("\n");

    return 0;

}

This program maintains the BST property during insertion. Inorder traversal prints the tree in ascending order, confirming the correct placement of nodes.

Program 2: Searching in BST

This program shows how to search for a specific value in a BST efficiently by leveraging the BST property.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Recursive search function
Node* search(Node *root, int key) {

    if (root == NULL || root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    int key = 60;
    Node *found = search(root, key);

    if (found != NULL)
        printf("%d found in BST.\n", key);
    else
        printf("%d not found in BST.\n", key);

    return 0;

}

Searching in a BST is efficient because at each node, you can decide whether to go left or right, eliminating half of the remaining nodes.

Program 3: Deletion in BST

This program demonstrates deletion of a node in BST while preserving the BST property.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Find minimum value node in a subtree
Node* findMin(Node* root) {

    while (root->left != NULL)
        root = root->left;

    return root;

}

// Delete a node from BST
Node* deleteNode(Node* root, int key) {

    if (root == NULL) return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);

    else if (key > root->data)
        root->right = deleteNode(root->right, key);

    else {

        // Node with only one child or no child
        if (root->left == NULL) {

            Node* temp = root->right;
            free(root);

            return temp;

        }
        else if (root->right == NULL) {

            Node* temp = root->left;
            free(root);

            return temp;

        }

        // Node with two children: get inorder successor
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}

// Inorder traversal (Left, Root, Right)
void inorder(Node *root) {

    if (root == NULL) return;

    inorder(root->left);

    printf("%d ", root->data);

    inorder(root->right);

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder before deletion: ");
    inorder(root);
    printf("\n");

    root = deleteNode(root, 50);

    printf("Inorder after deletion: ");
    inorder(root);
    printf("\n");

    return 0;

}

Deleting a node requires handling three cases: node with no children, node with one child, and node with two children. Using the inorder successor ensures that the BST property is preserved.

Program 4: Minimum in BST

This program demonstrates how to find the minimum value in a BST, which is always located in the leftmost node of the tree.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Find minimum value
Node* findMin(Node* root) {

    if (root == NULL) return NULL;

    while (root->left != NULL)
        root = root->left;

    return root;

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);

    Node* minNode = findMin(root);

    if (minNode != NULL)
        printf("Minimum value in BST: %d\n", minNode->data);

    return 0;

}

The minimum value in a BST is found by traversing left until no more left children exist. This works because smaller values are always stored in the left subtree. The algorithm runs in O(h) time, where h is the tree height.

Program 5: Maximum in BST

This program finds the maximum value in a BST, which is always located in the rightmost node.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Find maximum value
Node* findMax(Node* root) {

    if (root == NULL) return NULL;

    while (root->right != NULL)
        root = root->right;

    return root;

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 90);

    Node* maxNode = findMax(root);

    if (maxNode != NULL)
        printf("Maximum value in BST: %d\n", maxNode->data);

    return 0;

}

The maximum value in a BST is found by traversing right until no more right children exist. This works because larger values are always stored in the right subtree. Like the minimum operation, this runs in O(h) time.

Program 6: Floor in BST

This program finds the floor of a key in BST. The floor is the largest value less than or equal to the given key.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Find floor in BST
Node* floorInBST(Node* root, int key) {

    Node* res = NULL;

    while (root != NULL) {

        if (root->data == key)
            return root;
        else if (key < root->data)
            root = root->left;
        else {
            res = root;
            root = root->right;
        }

    }

    return res;

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 60);

    int key = 65;
    Node* floorNode = floorInBST(root, key);

    if (floorNode != NULL)
        printf("Floor of %d is %d\n", key, floorNode->data);
    else
        printf("No floor found for %d\n", key);

    return 0;

}

The floor operation works by tracking the candidate node whenever we go right. If the key is found exactly, that value is the floor. Otherwise, the best candidate encountered is returned.

Program 7: Ceil in BST

This program finds the ceil of a given key in BST. The ceil is the smallest value greater than or equal to the key.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Find ceil in BST
Node* ceilInBST(Node* root, int key) {

    Node* res = NULL;

    while (root != NULL) {

        if (root->data == key)
            return root;
        else if (key > root->data)
            root = root->right;
        else {
            res = root;
            root = root->left;
        }

    }

    return res;

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 60);

    int key = 55;
    Node* ceilNode = ceilInBST(root, key);

    if (ceilNode != NULL)
        printf("Ceil of %d is %d\n", key, ceilNode->data);
    else
        printf("No ceil found for %d\n", key);

    return 0;

}

The ceil operation keeps track of the smallest candidate whenever we move left. If the exact key exists in the BST, that node is returned. Otherwise, the smallest greater node is chosen as the ceil.

Program 8: Inorder Successor in BST

This program finds the inorder successor of a node in BST. The successor is the next higher value in the inorder traversal sequence.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Inorder successor function
Node* inorderSuccessor(Node* root, Node* target) {

    Node* succ = NULL;

    while (root != NULL) {

        if (target->data < root->data) {
            succ = root;
            root = root->left;
        } else {
            root = root->right;
        }

    }

    return succ;

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    Node* target = root->left; // Node with value 30
    Node* succ = inorderSuccessor(root, target);

    if (succ != NULL)
        printf("Inorder successor of %d is %d\n", target->data, succ->data);
    else
        printf("No inorder successor for %d\n", target->data);

    return 0;

}

If the node has a right child, the successor is the minimum in the right subtree. Otherwise, it is the lowest ancestor for which the node lies in its left subtree. This makes searching efficient in O(h) time.

Program 9: Inorder Predecessor in BST

This program finds the inorder predecessor of a node in BST. The predecessor is the next smaller value in the inorder traversal sequence.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert a node into the BST
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;

}

// Inorder predecessor function
Node* inorderPredecessor(Node* root, Node* target) {

    Node* pred = NULL;

    while (root != NULL) {

        if (target->data > root->data) {
            pred = root;
            root = root->right;
        } else {
            root = root->left;
        }

    }

    return pred;

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    Node* target = root->right; // Node with value 70
    Node* pred = inorderPredecessor(root, target);

    if (pred != NULL)
        printf("Inorder predecessor of %d is %d\n", target->data, pred->data);
    else
        printf("No inorder predecessor for %d\n", target->data);

    return 0;

}

If the node has a left child, the predecessor is the maximum in the left subtree. Otherwise, it is the lowest ancestor for which the node lies in its right subtree. Like successor, this runs in O(h) time.

Program 10: Handling Duplicates in BST

This program demonstrates handling of duplicate values in BST. One common method is to always insert duplicates into the left subtree.

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

// Structure for a BST node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Insert allowing duplicates (stored in left subtree)
Node* insert(Node* root, int value) {

    if (root == NULL)
        return createNode(value);
    if (value <= root->data) // <= handles duplicates
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);

    return root;

}

// Inorder traversal
void inorder(Node* root) {

    if (root == NULL) return;
    inorder(root->left);

    printf("%d ", root->data);
    inorder(root->right);

}

int main() {

    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 30); // duplicate
    insert(root, 70);
    insert(root, 50); // duplicate
    insert(root, 60);

    printf("Inorder traversal with duplicates: ");
    inorder(root);
    printf("\n");

    return 0;

}

Handling duplicates depends on the application. Some choose to store duplicates on the left, others on the right, and some maintain a count field inside each node. The method above ensures the BST property is preserved while allowing repeated values.

FAQs

Q1: What is the time complexity of BST operations?
Average case for search, insert, and delete: O(log n). Worst case (unbalanced tree): O(n).

Q2: Can BST store duplicate values?
Standard BSTs do not allow duplicates, but duplicates can be handled by either counting occurrences or placing duplicates consistently in one subtree.

Q3: What traversal is best to display BST in sorted order?
Inorder traversal prints BST nodes in ascending order.

Q4: How to balance a BST?
Balancing requires converting it into a self-balancing BST like AVL or Red-Black tree.

Conclusion

BSTs provide efficient storage and retrieval of sorted data. Correctly implementing insertion, search, and deletion operations while maintaining the BST property is crucial. Understanding BSTs forms the foundation for more advanced tree structures and algorithms.

References & Additional Resources

A selection of books and online resources providing both theoretical foundations and practical examples to understand Binary Search Trees (BST), their operations, and traversal techniques in C.

  1. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of BST concepts, insertions, deletions, and traversal algorithms.
  2. GeeksforGeeks: Binary Search Tree – Detailed explanation of BST properties and implementations in C.
  3. Programiz: BST Operations – Beginner-friendly guide covering insertion, deletion, and search operations.
  4. Tutorialspoint: Tree Traversals and Algorithms – Overview of tree operations and traversal methods.

Related Posts

Scroll to Top