root of a binary search tree: at every node, all values in the left subtree are smaller than the node's value and all values in the right subtree are larger. The tree may have grown lopsided, for example into a long chain.
Build a new search tree of minimum height from the same values, using this rule:
1. Write out all the values in increasing order.
2. The middle element of that list becomes the root. If the count is even and there are two middle elements, take the left one.
3. The elements to its left form the left subtree the same way, and the elements to its right form the right subtree.
Return the root of the new tree.root=tree_node([10, None, 20, None, 30, None, 40, None, 50]) → [30, 10, 40, None, 20, None, 50]
In sorted order the values are 10, 20, 30, 40, 50. The root is the middle one, 30; on the left, 10 and 20 give the left middle 10 as the subtree root, and on the right 40 and 50 give 40.
root=tree_node([7, 3, None, 1, 5]) → [3, 1, 5, None, None, None, 7]
The sorted values are 1, 3, 5, 7. There are two middle ones, 3 and 5, so the left one, 3, becomes the root.
root=tree_node([4]) → [4]
Node.val ≤ 10⁵root is a valid search treeroot=tree_node([10, None, 20, None, 30, None, 40, None, 50])
[30, 10, 40, None, 20, None, 50]
Run checks the first 3 tests in your browser. Submit checks all 27 tests on the server, hidden ones included.