A high-performance system stores sorted datasets such as:
- ranked user scores
- sorted logs
- ordered product listings
To enable fast querying, insertion, and lookup operations, the system needs to convert this sorted data into a Balanced Binary Search Tree (BST).
A balanced BST ensures:
- efficient search operations (
O(log n)) - minimal tree height
- optimal performance for large-scale systems
The system receives a sorted array and must convert it into a height-balanced BST.
A BST is considered height-balanced if:
the depth of the two subtrees of every node never differs by more than 1
This is a common coding interview problem frequently asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given a sorted array of integers nums (in ascending order), convert it into a height-balanced BST and return its root.
Input Format
nums: sorted integer array
Output Format
- Return the root node of the constructed BST
Each node:
TreeNode { int val; TreeNode left; TreeNode right;}
Examples
Example 1:
Input: nums = [-10,-3,0,5,9]
Output: 0
/ \
-3 9
/ /
-10 5
Explanation: Middle element becomes root → ensures balance
Example 2:
Input: nums = [1,3]
Output: 3
/
1