Java Program to Convert a Sorted Array to a Balanced Binary Search Tree

This Java program demonstrates how to convert a sorted array into a balanced Binary Search Tree (BST). The key to maintaining balance is to recursively select the middle element of the array as the root, which ensures that the resulting BST is height-balanced, optimizing the operations that depend on tree depth such as search, insert, and delete.

BinarySearchTree Class

The BinarySearchTree class includes a Node inner class and a method to convert a sorted array to a balanced BST.

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

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

    // Method to convert sorted array to a balanced BST
    public Node sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return sortedArrayToBSTHelper(nums, 0, nums.length - 1);
    }

    // Helper method to insert values into the BST
    private Node sortedArrayToBSTHelper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;
        Node node = new Node(nums[mid]);
        node.left = sortedArrayToBSTHelper(nums, start, mid - 1);
        node.right = sortedArrayToBSTHelper(nums, mid + 1, end);
        return node;
    }

    // Function to print the tree in inorder traversal
    public void inOrderPrint(Node node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.print(node.data + " ");
            inOrderPrint(node.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        Node root = bst.sortedArrayToBST(nums);

        System.out.println("Inorder traversal of constructed BST");
        bst.inOrderPrint(root);
    }
}

Explanation of the Methods

• sortedArrayToBST – Public method that initializes the conversion process. It handles edge cases and invokes the helper method.
• sortedArrayToBSTHelper – Recursive helper method that constructs the BST by finding the middle element of the current subarray, creating a node from it, and recursively doing the same for the left and right subarrays.
• inOrderPrint – Utility method to print the nodes of the BST in inorder, which verifies that the tree maintains the BST properties.

Conclusion

The provided Java implementation effectively converts a sorted array into a balanced BST. This construction method ensures optimal depth of the tree, which is crucial for maintaining efficient performance of depth-dependent operations.