Java Program to Find the Kth Smallest Element in a Binary Search Tree

This Java program identifies the kth smallest element in a Binary Search Tree (BST). Leveraging the properties of BSTs, where in-order traversal yields elements in a sorted order, the program efficiently finds the desired element.

BinarySearchTree Class

The BinarySearchTree class includes methods for inserting elements, in-order traversal, and finding the kth smallest element.

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

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

    Node root;
    int count = 0;

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

    private Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data < root.data) { root.left = insertRec(root.left, data); } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

    public int kthSmallest(int k) {
        count = k;
        return kthSmallestRec(root);
    }

    private int kthSmallestRec(Node root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }

        int left = kthSmallestRec(root.left);
        if (left != Integer.MIN_VALUE) {
            return left;
        }

        count--;
        if (count == 0) {
            return root.data;
        }

        return kthSmallestRec(root.right);
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(20);
        bst.insert(8);
        bst.insert(22);
        bst.insert(4);
        bst.insert(12);
        bst.insert(10);
        bst.insert(14);

        int k = 3;  // Find the 3rd smallest element
        System.out.println(k + "th smallest element is " + bst.kthSmallest(k));
    }
}

Explanation of the Methods

• insert – Inserts a new element into the BST while maintaining the BST properties.
• kthSmallest – Initiates the process to find the kth smallest element. It uses a counter to track how many elements have been processed.
• kthSmallestRec – A recursive helper method that traverses the tree in in-order and decrements the counter until it reaches zero, at which point the kth smallest element has been found.

Conclusion

This Java implementation efficiently finds the kth smallest element in a BST, demonstrating the utility of in-order traversal in exploiting the ordered properties of BSTs. This method is essential for applications that need to retrieve ordered data quickly, such as database management systems and memory allocation algorithms.