Convert Sorted Array to Balanced BST
In many applications, data needs to be stored and retrieved efficiently. Binary Search Trees (BSTs) are excellent data structures for this purpose, offering logarithmic time complexity for search, insertion, and deletion operations on average. However, if a BST becomes unbalanced, these operations can degrade to linear time. This problem challenges you to construct a balanced BST from a sorted array, ensuring optimal performance characteristics for subsequent operations.
You are given an integer array nums where the elements are sorted in ascending order and are unique. Your task is to convert this array into 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.
Implement the function sortedArrayToBST which takes the sorted array nums and returns the root of the constructed height-balanced BST.
nums — An array of integers, sorted in ascending order. All integers are unique.root of the constructed height-balanced Binary Search Tree. If the input array is empty, return null.nums is an empty array, the function should return null.Examples
Example 1
Input:
nums = [-10,-3,0,5,9]
Output:
[0,-3,9,-10,null,5]
Note:
One possible height-balanced BST. The root is 0, left child is -3, right child is 9. -3's left child is -10. 9's left child is 5.
Example 2
Input:
nums = [1,2,3,4]
Output:
[3,2,4,1]
Note:
Another valid height-balanced BST. The root is 3, left child is 2, right child is 4. 2's left child is 1.
Example 3
Input:
nums = [7]
Output:
[7]
Note:
A single-element array results in a single-node BST.
Example 4
Input:
nums = []
Output:
null
Note:
An empty array should return null.
Constraints
0 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums is sorted in a strictly increasing order.nums are unique.TreeNode class will be provided in the execution environment. Its definition is standard:
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
nums is always a sorted array of unique integers within the specified range).Loading editor...