1. Introduction to Binary Search Trees (BST)

A Binary Search Tree (BST) is a type of binary tree with the following properties:

• Left Subtree Property: The left child of a node contains only nodes with values less than the parent node.
• Right Subtree Property: The right child of a node contains only nodes with values greater than the parent node.
• Binary Tree Property: Each node has at most two children.

BSTs are widely used for searching, insertion, and deletion operations because they can maintain sorted data and provide efficient lookup, insertion, and deletion with an average-case time complexity of O(log n).

2. Insertion in a Binary Search Tree (BST)

Inserting a node into a BST follows a specific set of rules:

• If the tree is empty, the node becomes the root.
• If the value to be inserted is smaller than the root, recursively insert it in the left subtree.
• If the value to be inserted is greater than the root, recursively insert it in the right subtree.

Code for Insertion in a BST:

class Node {
    int data;
    Node left, right;

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

class BinarySearchTree {
    Node root;

    public BinarySearchTree() {
        root = null;
    }

    // Function to insert a new node into the BST
    public void insert(int data) {
        root = insertRec(root, data);
    }

    // Recursive function to insert a new node into the BST
    Node insertRec(Node root, int data) {
        // If the tree is empty, return a new node
        if (root == null) {
            root = new Node(data);
            return root;
        }

        // Otherwise, recur down the tree
        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);

        // Return the (unchanged) root pointer
        return root;
    }

    // In-order traversal to print the BST
    public void inOrder(Node root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + " ");
            inOrder(root.right);
        }
    }
}

Example:

public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        System.out.println("In-order traversal of the BST:");
        bst.inOrder(bst.root);  // Output: 20 30 40 50 60 70 80
    }
}

3. Deletion in a Binary Search Tree (BST)

Deleting a node from a BST can be more complex than insertion because there are three cases to consider:

1. Node to be deleted has no children: Simply remove the node.