Java Program for Basic Operations in a Binary Search Tree

This Java program demonstrates the basic operations of insertion, deletion, and search in a Binary Search Tree (BST). A BST is a binary tree in which each node has a key greater than all the keys in the node’s left subtree and less than those in its right subtree. This property makes the average time for each basic operation logarithmic to the number of keys in the tree under random insertions and moderate assumptions.

BinarySearchTree Class

The BinarySearchTree class includes methods for inserting, deleting, and searching for nodes, as well as a method to display the tree inorder for verification of tree structure.

public class BinarySearchTree {
    class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    Node root;

    BinarySearchTree() {
        root = null;
    }

    // Method to insert a new key
    void insert(int key) {
        root = insertRec(root, key);
    }

    // Recursive function to insert a new key
    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(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;
    }

    // Method to delete a key
    void deleteKey(int key) {
        root = deleteRec(root, key);
    }

    // Recursive function to delete a key
    Node deleteRec(Node root, int key) {
        if (root == null) return root;

        if (key < root.key) root.left = deleteRec(root.left, key); else if (key > root.key)
            root.right = deleteRec(root.right, key);
        else {
            // Node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // 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;
    }

    int minValue(Node root) {
        int minv = root.key;
        while (root.left != null) {
            minv = root.left.key;
            root = root.left;
        }
        return minv;
    }

    // Method to search a key
    boolean search(int key) {
        return searchRec(root, key);
    }

    // Recursive function to search a key
    boolean searchRec(Node root, int key) {
        if (root == null)
            return false;
        if (key == root.key)
            return true;
        return key < root.key ? searchRec(root.left, key) : searchRec(root.right, key);
    }

    // Inorder traversal
    void inorder() {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        System.out.println("Inorder traversal:");
        bst.inorder();

        System.out.println("\n\nDelete 20:");
        bst.deleteKey(20);
        bst.inorder();

        System.out.println("\n\nSearch for 30:");
        System.out.println(bst.search(30) ? "Found" : "Not Found");
    }
}

Explanation of the BST Methods

• insert – Adds a new node with the specified key in the correct location to maintain the BST properties.
• delete – Removes the node with the specified key, adjusting the tree structure as needed to maintain the BST properties.
• search – Checks whether a node with the specified key exists in the tree.
• inorder – Displays the keys in the tree in ascending order which also validates the structure of the BST.

Conclusion

This Java implementation provides a comprehensive guide to the essential operations of a Binary Search Tree. These operations are fundamental for many applications including database management systems and memory allocation processes.