Balanced Tree from a Sorted List

Easy

The list values is sorted in strictly increasing order. Build a binary search tree of minimum height from all of its elements using this rule: 1. The middle element of the list becomes the root. If the length is even and there are two middle elements, take the left one. 2. The elements to the left of it form the left subtree the same way, and the elements to the right form the right subtree. Return the root of the tree.

Example 1

values=[2, 5, 9, 14, 20] → [9, 2, 14, None, 5, None, 20]

The middle element 9 is the root. On the left, [2, 5]: of the two middles we take the left one, 2, and 5 becomes its right child. On the right, [14, 20]: root 14 with 20 on its right.

Example 2

values=[-3, 8] → [-3, None, 8]

With two elements the left middle, -3, is the root and 8 is its right child.

Example 3

values=[42] → [42]

A single element gives a one-node tree.

Constraints

1 ≤ len(values) ≤ 10⁴
−10⁴ ≤ values[i] ≤ 10⁴
values is strictly increasing

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Binary Search Tree Array Divide and Conquer Binary Tree

Similar problems

Other Orders for the Same Search Tree Hard Tree From Pre-Order and In-Order Walks Medium Tree From In-Order and Post-Order Walks Medium Tree From a Sorted Chain Medium Preorder of a Search Tree Medium

Input

values=[2, 5, 9, 14, 20]

Expected

[9, 2, 14, None, 5, None, 20]

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.