PreviousNext
Coding/Graphs and trees

Balanced BST from sorted array

Write codeMedium25 min

Your task

Given a strictly increasing sorted integer array nums, build a height-balanced BST and return its level-order encoding (include None for a present node's missing child, then trim trailing Nones). When a subarray has even length, choose the LEFT of the two middle elements as the root. Return [] for an empty array.

Examples

sorted_array_to_bst_levelorder(nums: list[int]) -> list
Example 1
Inputsorted_array_to_bst_levelorder([-10, -3, 0, 5, 9])
Output[0, -10, 5, None, -3, None, 9]