Data Structures and Algorithms in C (DSA)

📘 Chapter: Binary Search Tree (BST)

Following our exploration of general binary trees and their traversals, we now arrive at a highly specialized and incredibly useful variant: the Binary Search Tree (BST). A BST is a binary tree with a special ordering property that makes operations like searching, insertion, and deletion highly efficient, typically achieving logarithmic time complexity on average. This property makes BSTs foundational for many data management and retrieval systems.

🔍 What is a Binary Search Tree? The Core Property

A Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be Binary Search Trees.
• There are no duplicate keys (some definitions allow duplicates, placing them typically in the right subtree).

This ordering property ensures that an Inorder traversal of a BST will always yield the nodes' keys in sorted (non-decreasing) order.

🔧 Core Operations on a BST

1. Searching for a Node (Search)

To search for a key in a BST, we start at the root and recursively move down the tree.

• If the target key is equal to the current node's key, we've found it.
• If the target key is less than the current node's key, we search in the left subtree.
• If the target key is greater than the current node's key, we search in the right subtree.

// Search operation in C for BST
struct Node* search(struct Node* root, int key) {
    // Base Cases: root is null or key is present at root
    if (root == NULL || root->data == key)
        return root;

    // Key is greater than root's data
    if (root->data < key)
        return search(root->right, key);

    // Key is smaller than root's data
    return search(root->left, key);
}
  

Time Complexity: The time complexity of searching is O(h), where h is the height of the tree. In the best case (balanced tree), h = O(log n). In the worst case (skewed tree), h = O(n).

2. Inserting a Node (Insert)

To insert a new key, we follow the search path until we find a `NULL` pointer, which indicates the correct position for the new node.

• If the tree is empty, the new node becomes the root.
• Otherwise, compare the new key with the current node's key:
  • If smaller, go to the left subtree.
  • If larger, go to the right subtree.
• Insert the new node as a left or right child when a `NULL` link is encountered.

// Insert operation in C for BST
struct Node* insert(struct Node* node, int key) {
    // If the tree is empty, return a new node
    if (node == NULL)
        return createNode(key);

    // Otherwise, recur down the tree
    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key > node->data)
        node->right = insert(node->right, key);
    // Else (key == node->data), handle duplicates as per requirement (often ignore or add to right)

    return node;
}
  

Time Complexity: Similar to search, insertion takes O(h) time.

3. Deleting a Node (Delete)

Deletion is the most complex operation, as there are three cases to consider:

• Case 1: Node to be deleted is a Leaf Node (no children).

  Simply remove the node and set its parent's corresponding child pointer to `NULL`.

• Case 2: Node to be deleted has only One Child.

  Replace the node with its child. The child takes the node's position, and the node is removed.

• Case 3: Node to be deleted has Two Children.

  This is the most involved case. Find the inorder successor (smallest node in the right subtree) or the inorder predecessor (largest node in the left subtree) of the node to be deleted. Copy the value of the inorder successor (or predecessor) to the node, and then recursively delete the inorder successor (or predecessor) from its original position. The inorder successor will always have at most one right child (or no children), simplifying its deletion.

// Helper function to find the minimum value node in a BST
struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

// Delete operation in C for BST
struct Node* deleteNode(struct Node* root, int key) {
    // Base Case
    if (root == NULL) return root;

    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if (key < root->data)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if (key > root->data)
        root->right = deleteNode(root->right, key);

    // If key is same as root's key, then this is the node to be deleted
    else {
        // Node with only one child or no child
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // Node with two children: Get the inorder successor (smallest in the right subtree)
        struct Node* temp = minValueNode(root->right);

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

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

Time Complexity: Like search and insert, deletion also takes O(h) time.

🚀 Advantages and Disadvantages of BSTs

Advantages:

• Efficient Search, Insert, Delete (Average Case): On average, these operations take O(log n) time, making BSTs very fast for dynamic data.
• Ordered Traversal: Inorder traversal automatically gives elements in sorted order.
• Flexible Size: Can grow or shrink dynamically as elements are added or removed.

Disadvantages:

• Worst Case Performance: If elements are inserted in an already sorted (ascending or descending) order, the BST degenerates into a skewed tree, resembling a linked list. In this worst case, operations become O(n), losing the logarithmic advantage.
• No Guaranteed Balance: Basic BSTs do not guarantee balance, leading to the worst-case scenario. This is where self-balancing BSTs (like AVL trees or Red-Black trees) come into play.

Binary Search Tree Example Visualization

📌 Real-Life Example (UdaanPath)

On a platform like UdaanPath, Binary Search Trees would be crucial for managing and quickly accessing ordered data:

• User Account Management: If user IDs or usernames are unique and follow some ordering, a BST can efficiently store and retrieve user profiles. When a user logs in, their ID can be quickly searched.
• Course ID Lookup: Similar to our previous discussion, a BST storing courses by unique course IDs would allow for very fast lookup when a student searches for a specific course or when the system needs to fetch course details.
• Quiz Score Tracking: For a specific quiz, if you need to quickly find a student's score, or retrieve all scores within a certain range (e.g., all students who scored between 70 and 80), a BST can facilitate these range queries efficiently (though specialized structures like Segment Trees are better for complex range queries, BSTs offer a fundamental approach).
• Lexicographical Ordering of Content: If UdaanPath has a large database of articles, tutorials, or FAQs, organizing them in a BST based on their titles (alphabetically) could enable very quick search and retrieval.

✅ Summary: Ordered Efficiency

• A Binary Search Tree (BST) is a binary tree where for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger.
• It provides average O(log n) time complexity for search, insertion, and deletion operations, due to its ability to prune half of the remaining tree at each step.
• Inorder traversal of a BST yields elements in sorted order.
• Its main disadvantage is that it can degenerate to a skewed tree (like a linked list) in the worst-case scenario (O(n) operations), losing its efficiency.
• BSTs are widely used in databases, file systems, and dictionaries for efficient data storage and retrieval.

📤 Coming Next: AVL Trees (Self-balancing BST)

Recognizing the vulnerability of basic BSTs to worst-case performance, the next logical step is to explore ways to maintain balance. In the upcoming chapter, we will dive into AVL Trees, the first self-balancing binary search tree, which automatically rebalances itself after insertions and deletions to guarantee O(log n) performance for all operations, even in the worst case.