108. Convert Sorted Array to Binary Search Tree
You get an integer array nums whose values are distinct and sorted in strictly increasing order. Build a height-balanced binary search tree out of it — a tree where the two subtrees of every node differ in height by at most one — and return the root.
The sorted array is exactly the BST's inorder sequence, so choosing any element as the root sends everything before it into the left subtree and everything after it into the right. Balance comes from always choosing the middle.
Canonical form (so exactly one answer is correct): whenever a range has an even number of elements, make the left of its two middle elements the root of that range.
The judge prints your tree in level order with null marking a missing child of a present node, dropping trailing null markers.
Example 1:
Input: nums = [-10, -3, 0, 5, 9]
Output: [0, -10, 5, null, -3, null, 9]
Explanation: The middle value 0 becomes the root. The left half [-10, -3] has two middles; the left one, -10, is its root with -3 as a right child. The right half [5, 9] roots at 5 with 9 to its right.
Example 2:
Input: nums = [1, 3]
Output: [1, null, 3]
Explanation: Two elements have two middles; the canonical choice is the left one, so 1 is the root and 3 hangs to its right.
Constraints:
- 1 ≤ nums.length ≤ 2000
- -10⁴ ≤ nums[i] ≤ 10⁴
- nums is strictly increasing (all values distinct).
Hints:
In a BST, an inorder walk visits values in sorted order — so `nums` already tells you the inorder sequence of the answer. Which element should the root be so both sides get half the values?
Take the middle element as the root, then solve the two halves the same way: the left half builds the left subtree, the right half the right subtree. Splitting in half at every step is what keeps the height logarithmic.
Recurse on index bounds `(lo, hi)` with `mid = (lo + hi) / 2` (floor) instead of copying subarrays — that meets the required left-middle convention and keeps the build at O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [-10, -3, 0, 5, 9]
Expected output: [0, -10, 5, null, -3, null, 9]