Convert Sorted Array to BST
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]]
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;}