Convert Sorted Array to Binary Search Tree — Solution

Problem

Given a sorted array of integers, build a height-balanced BST from it — one where the depth of every leaf never differs by more than 1. Because the array is already sorted, any element you choose as the root automatically satisfies the BST property for every element to its left and right.

Example:

[0,-10,5,null,-3,null,9]

• Input: nums = [-10, -3, 0, 5, 9]
• Output: the tree shown above (or any other valid height-balanced BST)
• Explanation: 0 is the root; -10 and 5 are its children; -3 is the right child of -10; 9 is the right child of 5.

A different valid answer would place -3 as the left child of 0 with -10 under it — the problem accepts any valid height-balanced BST.

Intuition

Every midpoint in a sorted array is the ideal root for a subtree: exactly half the remaining elements go left, half go right, keeping both sides balanced. Repeating this recursively — always picking the midpoint — guarantees the depth never skews more than one level. No sorting or reordering is needed because the input is already sorted.

Solution — Divide and Conquer

Pick the middle element as the root, then recursively build the left subtree from the left half and the right subtree from the right half. The recursion bottoms out when the subarray is empty.

1. Return null if left > right (empty subarray — base case).
2. Compute mid = left + (right - left) // 2 to avoid integer overflow in Java/C++.
3. Create a node with nums[mid] as its value.
4. Recurse into [left, mid - 1] to build the left subtree.
5. Recurse into [mid + 1, right] to build the right subtree.
6. Return the root node.

1def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
2    def build(left: int, right: int) -> Optional[TreeNode]:
3        if left > right:
4            return None
5
6        mid = left + (right - left) // 2  # safe midpoint — avoids overflow in other languages
7        root = TreeNode(nums[mid])
8        root.left = build(left, mid - 1)
9        root.right = build(mid + 1, right)
10        return root
11
12    return build(0, len(nums) - 1)

Time: O(n) — each element is visited exactly once to create its tree node.

Space: O(log n) — the recursion stack depth equals the height of the balanced tree, which is ⌊log₂n⌋ + 1.

Complexity Summary

Common Mistakes

• Using (left + right) / 2 as the midpoint — in Java and C++, if both indices are large, their sum overflows a 32-bit integer; left + (right - left) / 2 is the safe form.
• Passing mid instead of mid - 1 as the upper bound for the left subarray — this accidentally includes the root's value in the left subtree, violating the BST property.
• Forgetting the base case — without if left > right: return None, the recursion never terminates.
• Expecting a single correct answer — the problem accepts any height-balanced BST; tests that compare against one specific tree output will incorrectly fail valid solutions.
• Confusing left-middle vs. right-middle — picking mid = left + (right - left) / 2 (left-center) or mid = left + (right - left + 1) / 2 (right-center) both produce valid height-balanced trees; the two choices simply mirror which side ends up one node taller when the subarray length is even.

Related Problems

• Construct Binary Tree from Preorder and Inorder Traversal — same divide-and-conquer structure, but the split point comes from the preorder array instead of the midpoint
• Construct Binary Tree from Inorder and Postorder Traversal — analogous reconstruction problem using different traversal orderings
• Kth Smallest Element in a BST — leverages the sorted inorder property of BSTs, the inverse of what this problem builds
• Balanced Binary Tree — verifying the height-balance property this problem guarantees by construction
• Binary Tree Level Order Traversal — useful for visualizing and reasoning about the level structure of the tree produced here