Convert Sorted Array to Binary Search Tree
Convert a sorted array into a height-balanced BST.
Examples
Input: [-10,-3,0,5,9]
Output: {"inorder":[-10,-3,0,5,9],"balanced":true}
Input: [1,3]
Output: {"inorder":[1,3],"balanced":true}
Hints
To ensure the BST is height-balanced, the root should be the middle element of the sorted array, splitting the remaining elements into left and right subarrays for the left and right subtrees.
Implement a recursive helper function that takes the left and right indices of the current subarray, calculates the middle index, creates a TreeNode with the middle element, and recursively constructs the left and right subtrees from the left and right subarrays.
Handle edge cases where the subarray is empty (return null) or has one element (return a leaf node), and ensure the recursion terminates correctly by adjusting the left and right indices in each recursive call.
Related Problems
Convert Sorted Array to Binary Search Tree
Convert a sorted array into a height-balanced BST.