Convert Sorted Array to BST
You are given an integer array sorted in ascending order. Your task is to convert it into a height-balanced Binary Search Tree (BST).
A BST is considered height-balanced if:
- The depths of the left and right subtrees of every node differ by at most one.
- The BST property is maintained throughout the tree.
Return the root of any valid height-balanced BST.
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: Picking the middle element as the root at each step produces a height-balanced BST. Other valid balanced BSTs are also accepted.
Input: nums = [1,3]
Output: [3,1]
Explanation: Either element may be chosen as the root; the resulting BST must remain height-balanced.
Input: nums = []
Output: []
Explanation: An empty array produces an empty tree.
- 0 = Array length = 104
- -10? = nums[i] = 10?
- nums is sorted in strictly ascending order
- A common approach is to repeatedly choose the middle element of the current subarray as the root, ensuring that the resulting tree remains balanced.
See how the best solutions work
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Keep every attempt
Your submissions, results and runtime history live here. Sign in to start your streak.
1 2 3 4 5 6 7
4 2 6 1 3 5 7
2 4 6 8 10
6 4 8 2 null null 10