A librarian has catalogue numbers already sorted in ascending order and wants them stored in a height-balanced binary search tree: for every node, the heights of its two subtrees differ by at most one. Write shelf_tree(values) returning the root TreeNode. To make the answer unique, always use the element at index len(slice) // 2 of the current slice as the root of that slice.
Tests display the tree via tree_to_list (level order with None gaps).
Examples
Input: values = [1, 2, 3, 4, 5]
Output: tree_to_list(...) = [3, 2, 5, 1, None, 4]
Explanation: 3 is the root; [1, 2] gives node 2 with left child 1; [4, 5] gives node 5 with left child 4.
Input: values = []
Output: []
Constraints
0 <= len(values) <= 10**4, strictly increasing integers.- Recursion depth is about log2(n).
Goals
- Choose the middle element as the root so the two subtrees have balanced sizes
- Build left and right subtrees from the two remaining slices
- Return None for an empty slice so leaves terminate the recursion