Convert Sorted Array to Binary Search Tree

def sorted_array_to_bst(nums):
    def build(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node
    return build(0, len(nums) - 1)

Convert Sorted Array to Binary Search Tree. Given a sorted array, build a height balanced search tree: smaller left, larger right, and every node's two sides differ in height by at most one.

Minus ten, minus three, zero, five, nine can become zero at the root, minus three and nine below it, then minus ten and five. Any balanced shape counts: one and three gives three over one, or one over three.

The naive way: insert values one by one. Sorted input always turns right, so the tree becomes a chain n tall, costing n squared.

The key idea: divide and conquer. The middle element becomes the root. The left half builds the left subtree, the right half the right. The halves differ in size by at most one, so the tree stays balanced. It's Binary Search's middle pick, used to build instead of to find.

In code, build takes a range, low to high. An empty range returns nothing. Otherwise, make a node from the middle, build the left half, then the right half, and return it.

Now minus ten through nine. The middle, index two, is zero: the root. The left half picks index zero: minus ten, with minus three on its right. The right half picks five, with nine on its right. Rounding up instead gives LeetCode's answer; both are balanced.

Each element becomes one node: linear time. The recursion is only log n deep: order log n extra space.

Pick the middle, build both halves, stay balanced. That's Convert Sorted Array to Binary Search Tree.