🌳 Binary Search Tree (BST) – Comprehensive Study Guide

A **Binary Search Tree (BST)** is a special type of **binary tree** where each node follows these rules:

  • 🔢 **Left subtree** contains values **less than** the node.
  • 🔢 **Right subtree** contains values **greater than** the node.
  • 🔄 Both left and right subtrees must also be **BSTs**.

⚡ Why Use a Binary Search Tree?

  • ✅ **Efficient Searching** – O(log n) complexity.
  • ✅ **Dynamic & Sorted Data Storage** – Automatically keeps data sorted.
  • ✅ **Fast Insertion & Deletion** – O(log n) average time complexity.
  • ✅ **Used in Databases, Filesystems, and AI-based decision trees.**

🛠️ Representation of a BST

1️⃣ **Using Arrays (For Complete BSTs)**


                int bst[] = {10, 5, 20, 3, 7, 15, 25}; // BST stored in an array

2️⃣ **Using Pointers (Dynamic Representation)**


                struct Node {
                    int data;
                    Node* left;
                    Node* right;
                };

🔄 Operations on BST

📌 **1. Insertion in BST**

Insert a node following the BST property.


                Node* insert(Node* root, int value) {
                    if (root == NULL) return new Node(value);
                    if (value < root->data) root->left = insert(root->left, value);
                    else root->right = insert(root->right, value);
                    return root;
                }

🔍 **2. Searching in BST**


                bool search(Node* root, int key) {
                    if (root == NULL) return false;
                    if (root->data == key) return true;
                    return (key < root->data) ? search(root->left, key) : search(root->right, key);
                }

❌ **3. Deletion in BST**

Remove a node while maintaining the BST structure.


                Node* deleteNode(Node* root, int key) {
                    if (!root) return root;
                    if (key < root->data) root->left = deleteNode(root->left, key);
                    else if (key > root->data) root->right = deleteNode(root->right, key);
                    else {
                        if (!root->left) return root->right;
                        if (!root->right) return root->left;
                        Node* temp = findMin(root->right);
                        root->data = temp->data;
                        root->right = deleteNode(root->right, temp->data);
                    }
                    return root;
                }

📌 **4. Traversals in BST**

➡️ **Inorder Traversal (Left → Root → Right)**

Prints elements in **sorted order**.


                void inorder(Node* root) {
                    if (root) {
                        inorder(root->left);
                        cout << root->data << " ";
                        inorder(root->right);
                    }
                }

➡️ **Preorder Traversal (Root → Left → Right)**


                void preorder(Node* root) {
                    if (root) {
                        cout << root->data << " ";
                        preorder(root->left);
                        preorder(root->right);
                    }
                }

➡️ **Postorder Traversal (Left → Right → Root)**


                void postorder(Node* root) {
                    if (root) {
                        postorder(root->left);
                        postorder(root->right);
                        cout << root->data << " ";
                    }
                }

⚖️ Self-Balancing Binary Search Trees

  • 📌 **AVL Tree** – Balances itself using **rotations**.
  • 📌 **Red-Black Tree** – Used in **C++ STL maps & sets**.
  • 📌 **B-Trees** – Used in **databases & file systems**.

⏳ Time Complexity Analysis

Operation Best Case Worst Case
Search O(log n) O(n)
Insertion O(log n) O(n)
Deletion O(log n) O(n)

🌍 Real-World Applications of BST

  • 📂 **Database Indexing** – Used in **B-Trees for efficient searches**.
  • 🔍 **Auto-Suggestion in Search Engines** – Used in **prefix search trees**.
  • 📡 **Networking (Routing Tables)** – Used in **IP lookup tables**.
  • ⚡ **Symbol Table Management in Compilers** – Used in **syntax parsing**.

🔗 Next Topics