Tree From a Sorted Chain

Medium

You are given head, the first node of a singly linked list whose values are in non-decreasing order. Build a balanced search tree from them using this rule: - the root is the middle element of the list; if the count is even, take the left of the two middle elements; - the elements to its left form the left subtree by the same rule, and the elements to its right form the right subtree; - an empty part gives an empty subtree. Return the root of the tree (None for an empty list).

Example 1

head=list_node([1, 3, 6, 8, 12, 15]) → [6, 1, 12, None, 3, 8, 15]

Six values have two middles, so we take the left one, 6. That leaves [1, 3] on the left (root 1, with 3 on its right) and [8, 12, 15] on the right (root 12).

Example 2

head=list_node([-4, 0, 7]) → [0, -4, 7]

The root is 0, with -4 and 7 on either side.

Example 3

head=list_node([]) → None

Constraints

0 ≤ number of nodes ≤ 2 · 10⁴
-10⁵ ≤ Node.val ≤ 10⁵
Values in the list are non-decreasing

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Binary Search Tree Linked List Divide and Conquer Binary Tree

Similar problems

Rebalance a Search Tree Medium Balanced Tree from a Sorted List Easy Other Orders for the Same Search Tree Hard Counting Search Tree Shapes Medium Is It a Search Tree? Medium

Input

head=list_node([1, 3, 6, 8, 12, 15])

Expected

[6, 1, 12, None, 3, 8, 15]

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