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.
Examples
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.
Hints
Hint 1
A common approach is to repeatedly choose the middle element of the current subarray as the root, ensuring that the resulting tree remains balanced.
Constraints
- 0 = Array length = 104
- -10? = nums[i] = 10?
- nums is sorted in strictly ascending order
Companies
Topics
Solution.cs C#JavaPythonC++Javascript
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions