Tree.java

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

        // 🟢 Insert values
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int val : values) {
            tree.insert(val);
        }

        // 📋 Traversals
        System.out.println("In-Order Traversal (Sorted):");
        tree.inOrderTraversal(tree.root);  // Output: 20 30 40 50 60 70 80
        System.out.println();

        System.out.println("Pre-Order Traversal:");
        tree.PreOrderTraversal(tree.root);  // Output: 50 30 20 40 70 60 80
        System.out.println();

        System.out.println("Post-Order Traversal:");
        tree.PostOrderTraversal(tree.root);  // Output: 20 40 30 60 80 70 50
        System.out.println();

        // Checking Search
        tree.booleanSearch(30);
        tree.booleanSearch(9);

        // 🍂 Case 1: Delete Leaf Node (20)
        System.out.println("Deleting leaf node: 20");
        tree.delete(20);
        tree.inOrderTraversal(tree.root);  // Should not include 20 anymore
        System.out.println("\n");

        // 🌿 Case 2: Delete Node with One Child (30)
        System.out.println("Deleting node with one child: 30");
        tree.delete(30);
        tree.inOrderTraversal(tree.root);  // Should not include 30, subtree should re-balance
        System.out.println("\n");

        // 🌳 Case 3: Delete Node with Two Children (50)
        System.out.println("Deleting node with two children: 50");
        tree.delete(50);
        tree.inOrderTraversal(tree.root);  // 50 should be replaced by in-order successor
        System.out.println("\n");

        // 🔍 Final check
        System.out.println("Final Tree (Level-Order Traversal):");
        tree.inOrderTraversal(tree.root);  // Bonus: show overall structure


    }

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

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

    public static class BinarySearchTree {
        Node root;

        public BinarySearchTree() {
            root = null;
        }

        public void insert(int data) {
            root = insertRecursive(root, data);
        }

        private Node insertRecursive(Node node, int data) {
            if (node == null) return new Node(data);

            if (data < node.data) {
                node.left = insertRecursive(node.left, data);
            } else if (data > node.data) {
                node.right = insertRecursive(node.right, data);
            }
            return node;
        }

        public void inOrderTraversal(Node node) {
            if (node != null) {
                inOrderTraversal(node.left);
                System.out.println(node.data + "");
                inOrderTraversal(node.right);
            }
        }

        public void PreOrderTraversal(Node node) {
            if (node != null) {
                System.out.println(node.data + "");
                PreOrderTraversal(node.left);
                PreOrderTraversal(node.right);
            }
        }

        public void PostOrderTraversal(Node node) {
            if (node != null) {
                PostOrderTraversal(node.left);
                PostOrderTraversal(node.right);
                System.out.println(node.data + "");
            }
        }

        public void booleanSearch(int data) {
            boolean result = searchRecursive(root, data);
            if (result) {
                System.out.println(data + " is present in the tree");
            } else {
                System.out.println(data + " isn't present in the tree");
            }
        }

        private boolean searchRecursive(Node node, int data) {
            if (node == null) return false;
            if (node.data == data) return true;

            return data < node.data
                    ? searchRecursive(node.left, data)
                    : searchRecursive(node.right, data);
        }

        public void delete(int data) {
            root = deleteRecursive(root, data);
        }

        private Node deleteRecursive(Node node, int data) {
            if (node == null) return null;

            if (data < node.data) {
                node.left = deleteRecursive(node.left, data);
            } else if (data > node.data) {
                node.right = deleteRecursive(node.right, data);
            } else {
                if (node.left == null && node.right == null) {
                    return null;
                }
                if (node.left == null) {
                    return node.right;
                } else if (node.right == null) {
                    return node.left;
                }
                int minValue = findMin(node.right);
                node.data = minValue;
                node.right = deleteRecursive(node.right, minValue);
            }
            return node;
        }

        private int findMin(Node node) {
            while (node.left != null) {
                node = node.left;
            }
            return node.data;
        }
    }
}