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.
Objective: Convert the sorted array into BST
Constraints:
1. 1 <= nums.length <= 10^4
2. -10^4 <= nums[i] <= 10^4
3. nums is sorted in a strictly increasing order.
Edge Cases:
Additional Details:
How it works:
1. Slice the nums array into half.
2. Create TreeNode with the middle value of nums array.
3. Assign left and right child of the node using recursion with the left and right end of nums array.
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
index = len(nums) // 2
left_index = index // 2
right_index = index + ((len(nums) - index) // 2)
node = TreeNode(val = nums[index])
if nums[index] == nums[left_index]:
node.left = None
else:
node.left = self.sortedArrayToBST(nums[0:index])
if nums[index] == nums[right_index]:
node.right = None
else:
node.right = self.sortedArrayToBST(nums[index+1:])
return node
Limitations:
1. It takes too much time and space due to array slicing.
How it works:
1. The recursive function is given with left and right boundary index values of nums array.
2. Set the middle index as the index value and recurse through the array.
3. Once the index value equals the left or right boundary value, they are given with None for left or right child node.
def sliceArray(self, nums, left, right):
index = left + (right - left + 1) // 2
node = TreeNode(val = nums[index])
if index == left:
node.left = None
else:
node.left = self.sliceArray(nums, left, index-1)
if index == right:
node.right = None
else:
node.right = self.sliceArray(nums, index+1, right)
return node
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
return self.sliceArray(nums, 0, len(nums)-1)
LeetCode Question #108