BST

class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;

    public TreeNode(int key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    // Insert a key into the BST
    public void insert(int key) {
        root = insertRec(root, key);
    }

    // Helper method to recursively insert a key into the BST
    private TreeNode insertRec(TreeNode root, int key) {
        if (root == null) {
            root = new TreeNode(key);
            return root;
        }

        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        return root;
    }

    // Inorder traversal of the BST
    public void inorder() {
        inorderRec(root);
        System.out.println();
    }

    // Helper method to recursively perform inorder traversal of the BST
    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }

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

    // Helper method to recursively delete a key from the BST
    private TreeNode deleteRec(TreeNode root, int key) {
        if (root == null)
            return root;

        // Search for the key to be deleted
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
        else {
            // Key found, delete this node

            // Case 1: Node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

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

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

        return root;
    }

    // Helper method to find the inorder successor (smallest in the right subtree)
    private int minValue(TreeNode node) {
        int minValue = node.key;
        while (node.left != null) {
            minValue = node.left.key;
            node = node.left;
        }
        return minValue;
    }

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

        // Insert elements into the BST
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // Inorder traversal of the BST
        System.out.println("Inorder traversal of BST:");
        tree.inorder();

        // Delete an element from the BST
        int keyToDelete = 30;
        System.out.println("Deleting key " + keyToDelete + " from BST");
        tree.delete(keyToDelete);

        // Inorder traversal after deletion
        System.out.println("Inorder traversal after deletion:");
        tree.inorder();
    }
}