Balanced Search Tree From a Sorted List

Given a list values sorted in non-decreasing order (it may contain repeated values), build a height-balanced binary search tree from it and return the root. Use exactly this rule so the answer is unique: for the range values[lo..hi] the root is values[(lo + hi) // 2], the elements before the middle form the left subtree and the elements after it form the right subtree. The inorder traversal of the result is therefore values itself.

Examples

      2
     / \
    1   3
     \   \
      2   5

Input:  values = [1, 2, 2, 3, 5]
Output: tree_to_list(...) == [2, 1, 3, None, 2, None, 5]

Input:  values = [4, 4, 4]
Output: [4, 4, 4]

Constraints

• 0 <= len(values) <= 1000
• values is sorted in non-decreasing order

Goals

• Split a sorted range at its middle to keep both halves balanced
• Recurse on index ranges rather than copying slices