Convert Sorted Array to Binary Search Tree Easy 0 attempts
LeetCode ↗

Convert Sorted Array to Binary Search Tree

Easy TreeBinary TreeDFS LeetCode

Given a sorted array, convert it to a height-balanced BST.

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

Sample Input
—
Sample Output
—
Constraints
  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in strictly increasing order
Topics
TreeBinary TreeDFS

Recursive Mid-Point

Pick the middle element as root, recurse on left and right halves.

function sortedArrayToBST(nums) {
  function build(lo, hi) {
    if (lo > hi) return null;
    const mid = (lo + hi) >> 1;
    return { val: nums[mid], left: build(lo, mid-1), right: build(mid+1, hi) };
  }
  return build(0, nums.length - 1);
}

Time: O(n) | Space: O(log n)

Saved in this browser only. Private to you.

JavaScript