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 Sam K., 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

More Trees practice problems

See all Trees problems →