bst

class TreeNode<T extends Comparable<T>> {
    T data;
    TreeNode<T> left, right;

    public TreeNode(T data) {
        this.data = data;
        this.left = this.right = null;
    }
}

public class BinarySearchTree<T extends Comparable<T>> {
    private TreeNode<T> root;

    public BinarySearchTree() {
        this.root = null;
    }

    // Insert operation
    public void insert(T data) {
        root = insertRec(root, data);
    }

    private TreeNode<T> insertRec(TreeNode<T> root, T data) {
        if (root == null) {
            root = new TreeNode<>(data);
            return root;
        }

        if (data.compareTo(root.data) < 0) {
            root.left = insertRec(root.left, data);
        } else if (data.compareTo(root.data) > 0) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    // Search operation
    public boolean search(T data) {
        return searchRec(root, data) != null;
    }

    private TreeNode<T> searchRec(TreeNode<T> root, T data) {
        if (root == null || root.data.equals(data)) {
            return root;
        }

        if (data.compareTo(root.data) < 0) {
            return searchRec(root.left, data);
        } else {
            return searchRec(root.right, data);
        }
    }

    // In-order traversal (sorted order)
    public void inOrder() {
        inOrderRec(root);
    }

    private void inOrderRec(TreeNode<T> root) {
        if (root != null) {
            inOrderRec(root.left);
            System.out.print(root.data + " ");
            inOrderRec(root.right);
        }
    }

    // Delete operation
    public void delete(T data) {
        root = deleteRec(root, data);
    }

    private TreeNode<T> deleteRec(TreeNode<T> root, T data) {
        if (root == null) {
            return null;
        }

        if (data.compareTo(root.data) < 0) {
            root.left = deleteRec(root.left, data);
        } else if (data.compareTo(root.data) > 0) {
            root.right = deleteRec(root.right, data);
        } else {
            // Node to be deleted found

            // Case 1: Node has no children (leaf node)
            if (root.left == null && root.right == null) {
                return null;
            }

            // Case 2: Node has only one child
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }

            // Case 3: Node has two children
            T minValue = findMinValue(root.right);
            root.data = minValue;
            root.right = deleteRec(root.right, minValue);
        }

        return root;
    }

    private T findMinValue(TreeNode<T> root) {
        T minValue = root.data;
        while (root.left != null) {
            minValue = root.left.data;
            root = root.left;
        }
        return minValue;
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> 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.println("In-order traversal:");
        bst.inOrder();
        System.out.println();

        System.out.println("Search 60: " + bst.search(60));
        System.out.println("Search 100: " + bst.search(100));

        bst.delete(70);

        System.out.println("In-order traversal after deleting 70:");
        bst.inOrder();
        System.out.println();
    }
}