Binary Search Tree (BST) in Data Structures

 A Binary Search Tree (BST) is a special type of Binary Tree that maintains elements in sorted order. It allows for efficient searching, insertion, and deletion operations.

---

📌 Properties of a Binary Search Tree (BST)

✔ Left Subtree Rule – The left child contains nodes with values less than the parent node.
✔ Right Subtree Rule – The right child contains nodes with values greater than the parent node.
✔ No Duplicate Values – Each value in the BST is unique.
✔ Inorder Traversal Results in Sorted Order – A BST, when traversed in inorder (LNR), returns elements in ascending order.

---

📌 Example of a BST

Tree Structure

        50
       /  \
     30    70
    /  \   /  \
   20   40 60  80

Array Representation (Level Order)

[50, 30, 70, 20, 40, 60, 80]

• Left of 50 → 30 (less than 50)
• Right of 50 → 70 (greater than 50)
• Left of 30 → 20, Right of 30 → 40
• Left of 70 → 60, Right of 70 → 80

---

📌 Operations on a BST

1️⃣ Searching in BST (O(log n))

• Compare the target value with the root.
• If it’s smaller, search the left subtree; if larger, search the right subtree.
• Repeat until the value is found or the subtree is empty.

🔹 Worst Case (Unbalanced Tree): O(n)
🔹 Best/Average Case (Balanced Tree): O(log n)

---

2️⃣ Insertion in BST (O(log n))

• Start at the root.
• Compare the new value with the root:
  • If smaller, move left.
  • If greater, move right.
• Insert it at the appropriate position when an empty spot is found.

🔹 Example: Inserting 25 in the above tree:

        50
       /  \
     30    70
    /  \   /  \
   20   40 60  80
      \
      25  <-- Inserted Here

---

3️⃣ Deletion in BST (O(log n))

Three cases for deletion:

1. Node with no child → Simply remove it.
2. Node with one child → Replace it with its child.
3. Node with two children → Replace it with its inorder successor (smallest value in the right subtree).

🔹 Example: Deleting 50

• The inorder successor of 50 is 60
• Replace 50 with 60, then delete the original 60

        60
       /  \
     30    70
    /  \      \
   20   40    80

---

📌 BST Code Implementation in C

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

// Define a Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Insert a node in BST
struct Node* insert(struct Node* root, int value) {
    if (root == NULL) return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);
    return root;
}

// Inorder Traversal (LNR) - Prints elements in sorted order
void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    struct 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: ");
    inorderTraversal(root);
    return 0;
}

🔹 Output:

Inorder Traversal of BST: 20 30 40 50 60 70 80

💡 This confirms that BST maintains elements in sorted order!

---

📌 Advantages of BST

✅ Efficient Searching (O(log n))
✅ Sorted Order Retrieval using Inorder Traversal
✅ Dynamic and Easy to Modify (Insert/Delete)

📌 Disadvantages of BST

❌ Unbalanced Trees Can Become Slow (O(n)) – If elements are inserted in sorted order, the tree becomes skewed.
❌ Balancing Needed – AVL and Red-Black Trees improve efficiency.

---

📌 When to Use a BST?

✔ Efficient Searching & Sorting – Used in databases, maps, and sets.
✔ Hierarchical Data Representation – Used in file systems and routers.
✔ Symbol Tables & Dictionaries – Used in compilers and natural language processing.

🌲 Binary Search Trees are a fundamental data structure for fast searching and efficient data management