โ† Amazon questions

Construct balanced BST from sorted list

Filed under Amazon

Free read 1 of 3

Understand 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

  1. Understand what constitutes a height-balanced BST and confirm input constraints.

Solution

O(N) time, O(N) space for recursion stack

Python
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.