Description:
Given an integer array nums where the elements are sorted in ascending order, convert it to 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.
Solution:
Time Complexity : O(n)
Space Complexity: O(n)
// The function will make the num in the center of the array the root node
// All nums to the left of the center num will be part of the left subtree and all nums to the right of the center num will be part of the right subtree
// Repeat this process of setting the center num in each subarray as the root node and all nums to the left and right as its sub trees
var sortedArrayToBST = function(nums) {
if (!nums.length) return null;
const mid = Math.floor(nums.length / 2);
const root = new TreeNode(nums[mid]);
// Call the function recursively on each subtree
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
Top comments (0)