You are given an integer array nums sorted in strictly increasing order. Build a height-balanced binary search tree that contains exactly these values and return its root. Height-balanced means that for every node, the heights of its two subtrees differ by at most 1. Any valid tree is accepted.
[0,-3,9,-10,null,5] is also accepted. Both are balanced BSTs.[3,1] is also accepted.- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in strictly increasing order
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Inserting the values one by one into a BST would give a straight chain of height n, because the input is sorted. To keep it balanced, the root must split the values into two halves of nearly equal size, which is exactly the middle element. The same rule applies recursively to each half, so every subtree is balanced and, since the array is sorted, the BST order holds automatically.
Algorithm
- Define
build(lo, hi)that builds a tree fromnums[lo..hi]. - If
lo > hi, return null. - Let
mid = (lo + hi) / 2and create a node withnums[mid]. - Set its left child to
build(lo, mid - 1)and right child tobuild(mid + 1, hi). - Return
build(0, n - 1).
O(n)Space: O(log n) recursion depthlo + (hi - lo) / 2 in Java and C++ to avoid integer overflow on huge ranges. A follow-up is the same task for a sorted linked list, where you find the middle with slow and fast pointers.class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: def build(lo, hi): if lo > hi: return None mid = (lo + hi) // 2 # middle element becomes the root node = TreeNode(nums[mid]) node.left = build(lo, mid - 1) node.right = build(mid + 1, hi) return node return build(0, len(nums) - 1)