Convert Sorted Array to Binary Search Tree

Given a sorted integer array, construct a height-balanced binary search tree. Pattern focus: Convert Sorted Array to BST. Always choose the middle element as the root so the left and right subtrees stay balanced; when two middles exist, use the left-middle element.

Input Format

nums = sorted integer array

Output Format

root of a height-balanced BST

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums must be sorted in strictly increasing order unless otherwise stated in the input format.

Examples

Example 1:

Input:

nums = [-10,-3,0,5,9]

Output:

[0,-3,9,-10,null,5]

Explanation:

The middle element 0 becomes the root, and the halves are built recursively.

Example 2:

Input:

nums = [1,3]

Output:

[1,null,3]

Explanation:

With two elements, the left-middle element 1 is chosen as the root.

Loading...
Convert Sorted Array to Binary Search Tree