Example: From Sorted Array to Balanced BST

The idea is to pick the middle element of the array as the root of the BST, then recursively construct the left and right subtrees using the elements to the left and right of the middle element, respectively. This ensures that the resulting BST is height-balanced.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // The idea is to pick the middle element of the array as the root of the BST, then 
        // recursively construct the left and right subtrees using the elements to the left and 
        // right of the middle element, respectively. This ensures that the resulting BST is 
        // height-balanced.
        
        if (nums == null || nums.length == 0) {
            return null;
        }
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    
    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        // Find the middle element of the array
        int mid = start + (end - start) / 2;

        // Create a new TreeNode with the middle element as the root
        TreeNode root = new TreeNode(nums[mid]);

        // Recursively construct the left and right subtrees
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);

        return root;
    }
}