Convert Sorted Array to BST (Recursive)

To convert a sorted array into a height-balanced binary search tree, I would use a recursive divide-and-conquer strategy. The core insight is that for a BST to be balanced, the root must be the median element of the current range, ensuring equal numbers of elements on both sides. First, I would define a helper function that accepts the array along with start and end indices. The base case occurs when the start index is greater than the end index; in this scenario, we return null. For the recursive step, I calculate the middle index using (start + end) / 2 to find the pivot. This middle element becomes the root of the current subtree. Then, I recursively call the function for the left half, passing the range from start to mid minus one, and assign the result to the root's left child. Similarly, I recurse for the right half, from mid plus one to end, assigning it to the right child. This process naturally builds a tree where the depth difference between any two leaves is at most one. Regarding complexity, since we visit each node exactly once, the time complexity is O(n). The space complexity is O(log n) because the recursion depth corresponds to the height of the balanced tree, which is logarithmic relative to the number of elements.