Binary Search Trees (BST): Insertion, Deletion, and Inorder/Preorder/Postorder Traversals in C

Author: Bhuban Subedi | Subject: Data Structures and Algorithms (CACS201) | Semester: Third Semester

In non-linear data structures, the Binary Search Tree (BST) is one of the most elegant and efficient concepts in computer science.

While searching through a linked list requires linear $O(N)$ time, a balanced Binary Search Tree reduces searching, insertion, and deletion times down to logarithmic $O(\log N)$ time by recursively halving the search space—similar to binary search in arrays.

In the Tribhuvan University (TU) BCA Third Semester DSA (CACS201) board examination, questions requiring you to construct a BST from a sequence of keys, perform tree traversals, or write the C function for deleting a node with two children appear consistently in 10-mark long questions.

In this guide, we will master the mathematical properties of BSTs, visualize recursive traversals, handle all three deletion cases, and write complete compilable C code.

1. What Is a Binary Search Tree (BST)?

A Binary Tree is a tree data structure in which each parent node has at most two children (referred to as the left child and right child).

A Binary Search Tree (BST) is a special binary tree that strictly satisfies the BST Ordering Property:
1. All keys stored in the left subtree of a node must be strictly less than ($<$) the node’s key.
2. All keys stored in the right subtree of a node must be strictly greater than ($>$) the node’s key.
3. Both the left and right subtrees must also be valid Binary Search Trees (recursive definition).

                     [ 50 ]  <-- Root
                    /      \
               [ 30 ]      [ 70 ]
              /      \    /      \
          [ 20 ]   [ 40 ][ 60 ]  [ 80 ]

2. Tree Traversals: Inorder, Preorder, and Postorder

Tree traversal refers to visiting every node in the tree exactly once in a systematic sequence.

+-------------------+---------------------------+--------------------------------------+
| Traversal Name    | Recursive Sequence        | Unique Property                      |
+-------------------+---------------------------+--------------------------------------+
| **Inorder**       | `Left -> Root -> Right`   | **Always produces sorted order** for |
|                   |                           | any valid Binary Search Tree!        |
+-------------------+---------------------------+--------------------------------------+
| **Preorder**      | `Root -> Left -> Right`   | Used to clone / serialize trees.     |
+-------------------+---------------------------+--------------------------------------+
| **Postorder**     | `Left -> Right -> Root`   | Used in bottom-up deletion & postfix |
|                   |                           | mathematical tree evaluations.       |
+-------------------+---------------------------+--------------------------------------+

Trace on Example Tree:

For the tree shown above:
– Inorder ($L \rightarrow V \rightarrow R$): 20, 30, 40, 50, 60, 70, 80 (Ascending Sorted!)
– Preorder ($V \rightarrow L \rightarrow R$): 50, 30, 20, 40, 70, 60, 80
– Postorder ($L \rightarrow R \rightarrow V$): 20, 40, 30, 60, 80, 70, 50

3. Node Deletion in BST: The 3 Critical Cases

While insertion is straightforward recursion, deleting a node from a BST requires careful structural restructuring to preserve the BST property.

       +-------------------------------------------------------------+
       |                  DELETION CASES IN A BST                    |
       +-------------------------------------------------------------+
       | Case 1: Node is a Leaf (0 children)                        |
       |         Simply free memory and set parent link to NULL.     |
       +-------------------------------------------------------------+
       | Case 2: Node has 1 Child (Left OR Right)                   |
       |         Bypass the node: Link parent directly to the child. |
       +-------------------------------------------------------------+
       | Case 3: Node has 2 Children                                |
       |         Find Inorder Successor (smallest in right subtree). |
       |         Copy Successor's value into current node.           |
       |         Recursively delete the Inorder Successor node.      |
       +-------------------------------------------------------------+

4. Complete C Implementation: Binary Search Tree

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

// BST Node Structure
struct TreeNode {
    int key;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Function prototypes
struct TreeNode* createNode(int item);
struct TreeNode* insert(struct TreeNode *node, int key);
struct TreeNode* search(struct TreeNode *root, int key);
struct TreeNode* findMin(struct TreeNode *node);
struct TreeNode* deleteNode(struct TreeNode *root, int key);
void inorder(struct TreeNode *root);
void preorder(struct TreeNode *root);
void postorder(struct TreeNode *root);

int main() {
    struct TreeNode *root = NULL;

    printf("--- BINARY SEARCH TREE (BST) MASTER DEMO ---\n");

    // Construct BST by inserting keys
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        root = insert(root, keys[i]);
    }

    printf("\n1. Inorder Traversal (Sorted Order):\n");
    inorder(root);
    printf("\n");

    printf("\n2. Preorder Traversal (Root First):\n");
    preorder(root);
    printf("\n");

    printf("\n3. Postorder Traversal (Bottom Up):\n");
    postorder(root);
    printf("\n");

    // Search Demo
    int searchVal = 40;
    if (search(root, searchVal) != NULL) {
        printf("\n>> Search: Key %d FOUND in BST!\n", searchVal);
    } else {
        printf("\n>> Search: Key %d NOT found.\n", searchVal);
    }

    // Deletion Demo: Delete node with 2 children (Node 50 - Root)
    printf("\nDeleting Root Node (50) which has 2 children...\n");
    root = deleteNode(root, 50);

    printf("Inorder Traversal after deleting 50:\n");
    inorder(root);
    printf("\n");

    return 0;
}

// Create new tree node
struct TreeNode* createNode(int item) {
    struct TreeNode *temp = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Recursive BST Insertion
struct TreeNode* insert(struct TreeNode *node, int key) {
    if (node == NULL) {
        return createNode(key);
    }
    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    }
    return node;
}

// Search a key in BST
struct TreeNode* search(struct TreeNode *root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }
    if (key < root->key) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

// Find minimum node (leftmost leaf) in a subtree
struct TreeNode* findMin(struct TreeNode *node) {
    struct TreeNode *curr = node;
    while (curr && curr->left != NULL) {
        curr = curr->left;
    }
    return curr;
}

// Delete a node from BST
struct TreeNode* deleteNode(struct TreeNode *root, int key) {
    if (root == NULL) return root;

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        // Node found! Handle the 3 cases:

        // Case 1 & 2: 0 or 1 child
        if (root->left == NULL) {
            struct TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode *temp = root->left;
            free(root);
            return temp;
        }

        // Case 3: 2 children
        // Get Inorder Successor (smallest in the right subtree)
        struct TreeNode *temp = findMin(root->right);

        // Copy successor's key to this node
        root->key = temp->key;

        // Delete the inorder successor from right subtree
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// Traversals
void inorder(struct TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

void preorder(struct TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct TreeNode *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->key);
    }
}

5. Time Complexity Analysis

+---------------+-----------------------+-----------------------+
| Operation     | Average Case (Balanced| Worst Case (Skewed)   |
+---------------+-----------------------+-----------------------+
| Search        | $O(\log N)$           | $O(N)$                |
| Insertion     | $O(\log N)$           | $O(N)$                |
| Deletion      | $O(\log N)$           | $O(N)$                |
| Traversal     | $O(N)$                | $O(N)$                |
+---------------+-----------------------+-----------------------+

Why does Skewing happen? If you insert already sorted keys (e.g., 10, 20, 30, 40, 50) into a normal BST, the tree degenerates into a single long branch (a degenerate/skewed tree) resembling a linked list, degrading search performance to $O(N)$. In Semester 3 DSA, self-balancing trees like AVL Trees solve this with automatic rotations.

Frequently Asked Questions (FAQ)

Q1: What is the Inorder Successor of a node in a BST?

The Inorder Successor of a node is the node with the smallest key that is strictly greater than the given node’s key. In a tree with a right subtree, it is simply the leftmost child in the right subtree.

Q2: What is the maximum number of nodes in a binary tree of height $h$?

A binary tree of height $h$ (where root is height 0) can have at most $2^{h+1} – 1$ nodes.