Binary Search Tree in Java

public class BinarySearchTreeDemo {

    // Node class
    static class Node {
        int data;
        Node left, right;

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

    // BinarySearchTree class
    static class BinarySearchTree {
        Node root;

        // Constructor
        BinarySearchTree() {
            root = null;
        }

        // Insert a new value into the BST
        void insert(int data) {
            root = insertRec(root, data);
        }

        // Recursive method to insert a new key in 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 node pointer
            return root;
        }

        // Search for a value in the BST
        boolean search(int data) {
            return searchRec(root, data);
        }

        // Recursive method to search a key in the BST
        boolean searchRec(Node root, int data) {
            // Base Cases: root is null or root's data is the key
            if (root == null) {
                return false;
            }
            if (root.data == data) {
                return true;
            }

            // Key is greater than root's data
            if (data > root.data) {
                return searchRec(root.right, data);
            }

            // Key is smaller than root's data
            return searchRec(root.left, data);
        }

        // Delete a value from the BST
        void delete(int data) {
            root = deleteRec(root, data);
        }

        // Recursive method to delete a key from the BST
        Node deleteRec(Node root, int data) {
            // Base case: root is null
            if (root == null) {
                return root;
            }

            // Recur down the tree
            if (data < root.data) {
                root.left = deleteRec(root.left, data);
            } else if (data > root.data) {
                root.right = deleteRec(root.right, data);
            } else {
                // Node with only one child or no child
                if (root.left == null) {
                    return root.right;
                } else if (root.right == null) {
                    return root.left;
                }

                // Node with two children: Get the inorder successor (smallest in the right subtree)
                root.data = minValue(root.right);

                // Delete the inorder successor
                root.right = deleteRec(root.right, root.data);
            }

            return root;
        }

        // Find the smallest value in a given tree
        int minValue(Node root) {
            int minValue = root.data;
            while (root.left != null) {
                minValue = root.left.data;
                root = root.left;
            }
            return minValue;
        }

        // Print the BST in inorder (sorted order)
        void inorder() {
            inorderRec(root);
            System.out.println();
        }

        // Recursive method for inorder traversal
        void inorderRec(Node root) {
            if (root != null) {
                inorderRec(root.left);
                System.out.print(root.data + " ");
                inorderRec(root.right);
            }
        }

        public static void main(String[] args) {
            BinarySearchTree tree = new BinarySearchTree();

            /* Let us create the following BST
                      50
                   /     \
                  30      70
                 /  \    /  \
                20   40  60   80
             */
            tree.insert(50);
            tree.insert(30);
            tree.insert(20);
            tree.insert(40);
            tree.insert(70);
            tree.insert(60);
            tree.insert(80);

            System.out.println("Inorder traversal of the BST:");
            tree.inorder(); // Output: 20 30 40 50 60 70 80

            System.out.println("Searching for 40 in the BST: " + tree.search(40)); // Output: true
            System.out.println("Searching for 90 in the BST: " + tree.search(90)); // Output: false

            System.out.println("Deleting 20 from the BST:");
            tree.delete(20);
            tree.inorder(); // Output: 30 40 50 60 70 80

            System.out.println("Deleting 30 from the BST:");
            tree.delete(30);
            tree.inorder(); // Output: 40 50 60 70 80

            System.out.println("Deleting 50 from the BST:");
            tree.delete(50);
            tree.inorder(); // Output: 40 60 70 80
        }
    }
}