Convert Sorted Array to Binary Search Tree

Problem

Given an integer array nums sorted in ascending order, convert it to a height-balanced binary search tree. (There may be multiple valid answers; any height-balanced BST whose inorder traversal is nums is accepted.) (LeetCode 108.)

Examples

        0
       / \
     -3   9
     /   /
  -10   5

Constraints

1 ≤ nums.length ≤ 10⁴ · strictly increasing values

Attempt it first

This is the direct payoff of the Balance & Why It Matters concept lesson's central warning: inserting a sorted array's elements ONE AT A TIME into a BST, in order, produces a completely degenerate tree (a linked list, O(n) height). This problem asks for the opposite outcome — guaranteed O(log n) height — from the exact same sorted data. Before opening anything, think about why picking the array's middle element as the root, recursively, sidesteps the degenerate-insertion problem entirely, rather than being a clever trick layered on top of insertion.