Convert Sorted Array to Binary Search Tree

To solve this problem efficiently, I would use a recursive divide-and-conquer approach. The core insight here is that since the input array is already sorted, we can guarantee a height-balanced tree by always choosing the middle element as the current node's root. This ensures that the number of nodes in the left and right subtrees differs by at most one. My implementation would involve a helper function that takes the start and end indices of the current subarray. First, I'd calculate the midpoint index. If the start index exceeds the end index, I return null, which serves as our base case. Otherwise, I create a new TreeNode using the value at the midpoint. Then, I recursively call this helper function for the left half (from start to mid-1) to construct the left child, and for the right half (from mid+1 to end) to construct the right child. For example, given the array [-10, -3, 0, 5, 9], the middle element 0 becomes the root. The left subarray [-10, -3] yields -3 as its root, and the right subarray [5, 9] yields 9. This structure naturally balances the tree. Regarding complexity, we visit each of the n elements exactly once to create a node, resulting in O(n) time complexity. The space complexity is O(log n) for the recursion stack because the tree remains balanced, keeping the maximum depth logarithmic relative to the input size.