Skip to main content

108. Convert Sorted Array to Binary Search Tree

easy

Build a height-balanced BST from a sorted array. The middle element of any range becomes the root of that subtree — divide-and-conquer in its purest tree form.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in a strictly increasing order.

Examples

Example 1

Input
nums = [-10,-3,0,5,9]
Output
[0,-3,9,-10,null,5]

Explanation: [0,-10,5,null,-3,null,9] is also a valid answer.

Example 2

Input
nums = [1,3]
Output
[3,1]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Picking the middle as the root guarantees balance, because left and right halves differ by at most one element.

Hint 2

Recurse on the left half for the left subtree and the right half for the right subtree.

Hint 3

Pass index bounds instead of slicing the array — slicing is O(n) per call and ruins the runtime.

Solution approach

Reveal approach

Index-based divide and conquer. Helper build(lo, hi): if lo > hi return null. Let mid = lo + (hi - lo) / 2 (floor division — picks left-middle for even-length ranges; right-middle also works). Create node with nums[mid]; set node.left = build(lo, mid - 1) and node.right = build(mid + 1, hi). Return node. Top-level call: build(0, nums.length - 1). Because each range is split in half, the resulting tree height is ceil(log2(n+1)), so it's balanced. O(n) time (each element visited once), O(log n) recursion space.

Complexity

Time
O(n)
Space
O(log n)

Related patterns

  • binary-search-tree
  • divide-and-conquer
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Convert Sorted Array to Binary Search Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →