Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Examples

Example 1:

Input: nums = [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5]

       0
      / \
    -3   9
    /   /
  -10  5

Explanation: [0, -10, 5, null, -3, null, 9] is also accepted.

Example 2:

Input: nums = [1, 3]
Output: [3, 1] or [1, null, 3]

    3      1
   /        \
  1          3

Example 3:

Input: nums = [1]
Output: [1]

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in strictly increasing order.

Expected Complexity

• Time: O(n)
• Space: O(log n) recursion stack, O(n) for the output tree