Convert Sorted Array to BST

Easy

Problem

Given a sorted array, build a height-balanced BST from it (the depths of the two subtrees of every node differ by at most 1).

Example 1

Input:  [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5] (any balanced BST is accepted)

Test cases

Case 1

Input:    [-10,-3,0,5,9]
Expected (any of): [[0,-10,5,null,-3,null,9],[0,-3,9,-10,null,5]]

Case 2

Input:    [1,3]
Expected (any of): [[1,null,3],[3,1]]

Case 3

Input:    [1]
Expected (any of): [[1]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Middle as root, recurse

Time O(n)Space O(log n)

Choosing the middle element keeps both halves equal in size, giving a height-balanced tree.

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