Convert a Sorted Array to a Balanced BST
Build a height-balanced binary search tree from an array sorted in ascending order.
Given an integer array nums sorted in strictly ascending order, construct a height-balanced binary search tree (BST) from it and return its root.
A height-balanced tree is one where, for every node, the heights of its left and right subtrees differ by at most 1.
Multiple height-balanced BSTs can be built from the same sorted array, so to make the answer unique, use this exact construction rule:
- Recursively pick the middle element of the current slice of the array to be the root of that subtree.
- If the current slice has an even number of elements (so there are two possible middle elements), always choose the one at the lower index (the left one of the two) as the root.
- Recurse the same way on the elements to the left of the chosen root (for the left subtree) and the elements to the right of it (for the right subtree).
Example 1
Input: nums = [1,2,3,4,5,6,7]
Output: [4,2,6,1,3,5,7]
Explanation: With an odd number of elements there's a single middle value (4), which becomes the root.
Example 2
Input: nums = [1,2,3,4]
Output: [2,1,3,null,null,null,4]
Explanation: The two possible middles are 2 and 3; the rule picks the lower-index one (2) as the root.
Example 3
Input: nums = []
Output: []
Explanation: An empty array produces an empty tree.
Constraints
- 1 <= nums.length <= 10000, or nums may be empty.
- -100000 <= nums[i] <= 100000
- nums is sorted in strictly ascending order, so all values are unique.
Follow-up
What would change if ties were broken by choosing the higher-index middle instead?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.