Show problems as
Classic problem #109MediumLinked ListDivide and ConquerTreeBinary Search TreeBinary Tree

Convert Sorted List to Binary Search Tree

Real-world version: Balanced Index Tree From A Reading Chain
Tracked in this browser only
Read Convert Sorted List to Binary Search Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMirror & Symmetry · Binary Trees & BST, animated step by step

A tape archive keeps its readings in one forward chain, already running from smallest to largest. The chain is handed to you as the list chain of its values, first link to last, and equal values may repeat.

Turn the chain into an index tree with this rule, which applies to any stretch of consecutive links:

  • An empty stretch produces no node.
  • Otherwise, if the stretch holds k links, the node takes the value at position k // 2 of the stretch, counting positions from 0. The links before that position form its left stretch and the links after it form its right stretch, and each is turned into a subtree by the same rule.

On a stretch of even length the rule therefore takes the upper of the two middle links. Walking the finished tree in order reproduces the chain, and at every node the taller side is ahead of the shorter by at most one level.

Return the tree as a level-order list. The first entry is the root's value; after that every node present contributes its left child and then its right child, writing null for a child that is absent. Nothing beneath an absent child is listed, and null entries at the very end are trimmed. An empty chain produces an empty list.

Examples

Example 1

Input
chain = [2,4,6,8]
Output
[6,4,8,2]

The stretch holds 4 links, so position 4 // 2 = 2 gives the root 6. Links [2,4] go left, and that stretch of 2 takes position 1, namely 4, with 2 hanging on its left. Link [8] goes right on its own.

Example 2

Input
chain = [7]
Output
[7]

A stretch of one link becomes a single node with both children absent, and their two trailing `null` entries are trimmed.

Example 3

Input
chain = [-9,-4,1,3,5,11,20]
Output
[3,-4,11,-9,1,5,20]

Position 7 // 2 = 3 gives the root 3. The stretch [-9,-4,1] yields -4 over -9 and 1, and the stretch [5,11,20] yields 11 over 5 and 20.

Example 4

Input
chain = [10,20]
Output
[20,10]

With 2 links the rule takes position 1, so 20 is the root and 10 becomes its left child. The root's absent right child is a trailing `null` and is trimmed.

Example 5

Input
chain = [1,1,2,2,2]
Output
[2,1,2,1,null,2]

Position 5 // 2 = 2 gives the root 2. The stretch [1,1] yields the second 1 with the first 1 on its left, and the stretch [2,2] yields the second 2 with the other 2 on its left.

Constraints

  • The number of links in chain is in the range [0, 2 * 10^4].
  • -10^5 <= chain[i] <= 10^5
  • chain is given in non-decreasing order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sorted_list_to_b_s_t(chain: list[int]) -> list:
Java
public TreeNode sortedListToBST(ListNode head)

More on the same topics