Construct balanced BST from sorted list
Filed under Amazon
Free read 1 of 3Understand what constitutes a height-balanced BST and confirm input constraints.
The question
Given a sorted array of integers, write a function to construct a height-balanced Binary Search Tree (BST). A height-balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Constraints
- The input array is sorted in ascending order.
- 1 <= array length <= 10^4
- -10^4 <= array[i] <= 10^4
Examples
- Input
- nums = [-10, -3, 0, 5, 9]
- Output
- [0, -3, 9, -10, null, 5]
- Why
- [0, -10, 5, null, -3, null, 9] is also a valid height-balanced BST.
Approach
Understand what constitutes a height-balanced BST and confirm input constraints.
Repeatedly insert elements one by one into an empty BST, which can lead to an unbalanced tree unless self-balancing trees are used (O(N log N)).
Use a recursive divide-and-conquer approach. Pick the middle element of the sorted array as the root to ensure balance, then recursively build the left and right subtrees from the left and right halves.
Empty array (returns null), single element array, and even vs odd length arrays.
Solution
O(N) time, O(N) space for recursion stack
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedArrayToBST(self, nums: list[int]) -> TreeNode:
def helper(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = helper(left, mid - 1)
node.right = helper(mid + 1, right)
return node
return helper(0, len(nums) - 1)
Tips
- What they are testing: Tests if you can apply divide-and-conquer principles and tree building recursively using array indices.
- Common mistake: Off-by-one errors when computing the middle index or slicing the array instead of passing index boundaries.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.