98. Convert Sorted Array to Binary Search Tree

Pick the middle element as the root so the two halves have (nearly) equal size — that guarantees balance. Recurse on the left half for the left subtree and the right half for the right subtree.

Idea

A height-balanced BST needs both subtrees of every node to be about the same size. Since the array is already sorted, choosing the middle element as the root splits the remaining elements into two halves of nearly equal length — the perfect recipe for balance. Everything left of the middle is smaller (left subtree) and everything right is larger (right subtree), so the BST ordering is automatic.

Algorithm

build(lo, hi) over index range:

1. If lo > hi, the range is empty → return None.
2. mid = (lo + hi) // 2; make nums[mid] the current node.
3. node.left = build(lo, mid - 1); node.right = build(mid + 1, hi).
4. Return node. Start with build(0, len(nums) - 1).

Worked example: [-10,-3,0,5,9]

• mid = 2 → root 0. Left half [-10,-3], right half [5,9].
• Left build(0,1): mid=0 → -10, right child build(1,1) → -3.
• Right build(3,4): mid=3 → 5, right child build(4,4) → 9.

Level-order: [0,-10,5,null,-3,null,9] — a balanced BST.

Complexity

• Time: O(n) — each element becomes exactly one node.
• Space: O(log n) recursion depth (the tree height).

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int mid = (lo + hi) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = build(nums, lo, mid - 1);
        node.right = build(nums, mid + 1, hi);
        return node;
    }
}