Binary Search Tree (BST)

1. Definition

A Binary Search Tree is a binary tree where:

• Left child < Parent node
• Right child > Parent node
• No duplicates (usually).

This property makes search, insert, and delete operations efficient (average O(log n)) if the tree is balanced.

2. Types of Binary Search Trees

1. Simple (Unbalanced) BST

   • Follows normal BST rules.

   • May become skewed (like a linked list) → O(n) operations in worst case.

2. Balanced BSTs
   These guarantee O(log n) height. Examples:

   • AVL Tree → Self-balancing using height factor (balance factor = -1, 0, 1).

   • Red-Black Tree → Balances using color properties.

   • Splay Tree → Recently accessed elements moved closer to root.

   • Treap → Combines BST + heap property.

   • B-Tree / B+Tree → Generalized BST used in databases.

3. Short Java Implementation of Simple BST

// Node structure
class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

// BST implementation
class BinarySearchTree {
    Node root;

    // Insert key
    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insertRec(root.left, key);
        else if (key > root.key) root.right = insertRec(root.right, key);
        return root;
    }

    // Search key
    boolean search(int key) {
        return searchRec(root, key);
    }

    boolean searchRec(Node root, int key) {
        if (root == null) return false;
        if (root.key == key) return true;
        return key < root.key ? searchRec(root.left, key) : searchRec(root.right, key);
    }

    // In-order Traversal (sorted order)
    void inorder() {
        inorderRec(root);
        System.out.println();
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }
}

// Demo
public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);

        System.out.print("Inorder Traversal: ");
        bst.inorder(); // 20 30 40 50 60 70 80

        System.out.println("Search 40: " + bst.search(40)); // true
        System.out.println("Search 100: " + bst.search(100)); // false
    }
}

✅ This is a basic BST (unbalanced).