Binary Search Tree

The BST (binary search tree) is a non-linear, recursive data structure that stores elements in sorted order, so that it can perform insertion, deletion, and search operations efficiently.

Each element in a BST is known as a node. Each node can have at most 2 children (child nodes). The left subtree of a node contains only nodes with values less than the node's value. The right subtree contains the node only nodes with values greater than the node's value.

The topmost node that doesn't have a parent is known as the root node. The node that doesn't have any children is known as the leaf node.

The average time complexity if O(log n) for insertion, deletion, and search operations.

import java.util.Scanner;
class Node{
    int key;
    Node left, right;
    public Node(int item){
        key = item;
        left = null;
        right = null;
    }
}
class BinarySearchTree{
    Node root;
    BinarySearchTree(){
        root = null;
    }
    Node insert(Node root, int key){
        if(root == null){
            root = new Node(key);
            return root;
        }
        if(key < root.key)
            root.left = insert(root.left, key);
        else if(key > root.key)
            root.right = insert(root.right, key);
        return root;
    }
    Node delete(Node root, int key){
        if(root == null)
            return root;
        if(key < root.key)
            root.left = delete(root.left, key);
        else if (key > root.key)
            root.right = delete(root.right, key);
        else{
            if(root.left == null)
                return root.right;
            else if(root.right == null)
                return root.left;
            root.key = minValue(root.right);
            root.right = delete(root.right, root.key);
        }
        return root;
    }
    int minValue(Node root){
        int minValue = root.key;
        while(root.left != null){
            minValue = root.left.key;
            root = root.left;
        }
        return minValue;
    }
    void inorder(Node root){
        if(root != null){
            inorder(root.left);
            System.out.print(root.key + " ");
            inorder(root.right);
        }
    }
    void preorder(Node root){
        if(root != null){
            System.out.print(root.key + " ");
            preorder(root.left);
            preorder(root.right);
        }
    }
    void postorder(Node root){
        if(root != null){
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.key + " ");
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        BinarySearchTree tree = new BinarySearchTree();
        while(true){
            System.out.println("1. Insert Node");
            System.out.println("2. Delete Node");
            System.out.println("3. Inorder Traversal");
            System.out.println("4. Preorder Traversal");
            System.out.println("5. Postorder Traversal");
            System.out.print("Enter your choice: ");
            int choice = Integer.parseInt(in.nextLine());
            switch(choice){
            case 1:
                System.out.print("Enter the key: ");
                int key = Integer.parseInt(in.nextLine());
                tree.root = tree.insert(tree.root, key);
                break;
            case 2:
                System.out.print("Key to delete: ");
                key = Integer.parseInt(in.nextLine());
                tree.root = tree.delete(tree.root, key);
                break;
            case 3:
                tree.inorder(tree.root);
                System.out.println();
                break;
            case 4:
                tree.preorder(tree.root);
                System.out.println();
                break;
            case 5:
                tree.postorder(tree.root);
                System.out.println();
                break;
            default:
                System.out.println("Bye!");
                return;
            }
        }
    }
}