BST.java

import java.util.Scanner;
public class BST {
    public class Node{
    private int value;
    private Node left;
    private Node right;
    private int height;

    public Node(int value){
        this.value=value;
    }
    public int getValue(){
        return value;
    }}
    private Node root;
    public BST() {}   //constructor

    public int height(Node node){
        if(node==null) return 0;
        return node.height;
    }
    public boolean isEmpty(){
        return root==null;
    }
    public void insert(int value){
        root=insert(value, root);
    }
    private Node insert(int value, Node node){
        if(node==null){
            node = new Node(value);
            return node;
        }
        if(value<node.value){
            node.left=insert(value, node.left);
        }
        if(value>node.value){
            node.right=insert(value, node.right);
        }
        node.height=Math.max(height(node.left),height(node.right))+1;
        return node;
    }
    public void populatedSorted(int[] nums) {
        populatedSorted(nums, 0, nums.length);
    }
    private void populatedSorted(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start+end) / 2;
        this.insert(nums[mid]);
        populatedSorted(nums, start, mid);
        populatedSorted(nums, mid+1, end);
    }
    public boolean balanced() {
        return balanced(root);
    }
    private boolean balanced(Node node){
        if(node==null){
            return true; }
        return Math.abs(height(node.left) - height(node.right)) <= 1 &&  balanced(node.left) && balanced(node.right);
    }
    private void display(){
        display(this.root, "Root node: ");
    }
    private void display(Node node, String details){
        if(node==null){
            return;
        }
        System.out.println(details + node.value);
        display(node.left, "Left child of "+node.value+": ");
        display(node.right, "Right child of "+node.value+": ");
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BST tree = new BST();
        while (true) {
            System.out.println("\nFor Binary Search Tree, choose one from the following: ");
            System.out.println("1. Insert elements manually");
            System.out.println("2. Insert sorted array (balanced BST)");
            System.out.println("3. Exit.");
            System.out.print("Enter your choice: ");
            int c = sc.nextInt();
            switch (c) {
                case 1 -> {
                    System.out.print("Enter number of elements to insert: ");
                    int n = sc.nextInt();
                    System.out.println("Enter the values:");
                    for (int i = 0; i < n; i++) {
                        int value = sc.nextInt();
                        tree.insert(value); }
                    if (tree.isEmpty()) {
                        System.out.println("Tree is empty.");
                    } else {
                        System.out.println("Binary Search Tree Structure: ");
                        tree.display();
                        System.out.println("Is the tree balanced? " + tree.balanced());
                    }}
                case 2 -> {
                    System.out.print("Enter number of sorted elements: ");
                    int n = sc.nextInt();
                    int[] arr = new int[n];
                    System.out.println("Enter the sorted values:");
                    for (int i = 0; i < n; i++) {
                        arr[i] = sc.nextInt(); }
                    tree.populatedSorted(arr);
                    if (tree.isEmpty()) {
                        System.out.println("Tree is empty.");
                    } else {
                        System.out.println("Binary Search Tree Structure: ");
                        tree.display();
                    }
                    if (tree.isEmpty()) {
                        System.out.println("Tree is empty.");
                    } else {
                        System.out.println("Is the tree balanced? " + tree.balanced());
                    }}
                case 3 -> {
                    System.out.println("Exiting program...");
                    sc.close();
                    return;
                }
                default -> System.out.println("Invalid choice! Please try again.");
            }}}}