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.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def sortedArrayToBST(self, nums):
9 return self._sortedArrayToBST(nums, 0, len(nums) - 1)
10
11 def _sortedArrayToBST(self, nums, left, right):
12 if left > right:
13 return None
14 mid = (left + right) // 2
15 node = TreeNode(nums[mid])
16 node.left = self._sortedArrayToBST(nums, left, mid - 1)
17 node.right = self._sortedArrayToBST(nums, mid + 1, right)
18 return nodeThis Python code uses two functions where one serves as a helper to recurse through the divided parts of the array to build a balanced BST.