Sponsored
Sponsored
This approach selects the middle element of the current array (or subarray) to ensure a balanced partitioning of elements, thus maintaining the height balance of the BST.
The middle element of the array becomes the root of the BST (or subtree), and the same operation is recursively applied to the left and right halves of the array to form the left and right subtrees respectively.
Time Complexity: O(n), where n is the number of elements in the array, because each element is visited once.
Space Complexity: O(log n) due to the recursion stack in a balanced tree scenario.
1function TreeNode(val, left = null, right = null) {
2 this.val = val;
3 this.left = left;
4 this.right = right;
5}
6
7function sortedArrayToBST(nums) {
8 function helper(left, right) {
9 if (left > right) return null;
10 let mid = Math.floor((left + right) / 2);
11 let node = new TreeNode(nums[mid]);
12 node.left = helper(left, mid - 1);
13 node.right = helper(mid + 1, right);
14 return node;
15 }
16 return helper(0, nums.length - 1);
17}This JavaScript function implements a helper function to recursively create nodes and define their left and right children to achieve an optimal BST structure from the middle items of the progressively halved subarrays.