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

Convert Sorted Array to Binary Search Tree

Easy TreeBinary TreeDFS LeetCode

You're given an array nums sorted in increasing order. Build a height-balanced binary search tree out of its values and return the root — meaning the two subtrees of any node never differ in depth by more than one.

Input Format
Implement sortedArrayToBST(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Returned trees are displayed as level-order arrays, trimming trailing nulls. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [1]
Output
[1]
Constraints
  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in strictly increasing order
Test Cases (2)
Case 1
Args: [[-10,-3,0,5,9]] Expected: [0,-10,5,null,-3,null,9]
Case 2
Args: [[1]] Expected: [1]
Topics
TreeBinary TreeDFS

Recursive Mid-Point

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

javascript
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