Given an array of distinct integers sorted in increasing order, build a height-balanced binary search tree containing them: one where the depths of every node's two subtrees differ by at most one.
Before you code
Inserting the values in order would build a chain. Which value should be the root so that each side receives half of the rest?
Hints
- Recurse on index ranges, lo and hi, rather than slicing, to keep it O(n).
- Make nums[mid] the root, then build the left subtree from lo to mid − 1 and the right from mid + 1 to hi.
- Return None for an empty range. Any choice of middle for even lengths is accepted.
Production & complexity notes
When solving Convert sorted array to binary search tree on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Why binary search trees degrade to reinforce the underlying pattern.
What it practices
Building a minimum-height tree from sorted keys, from Why binary search trees degrade.