Skip to main content

65. Convert Sorted Array to Binary Search Tree

easyAsked at Workday

Convert a sorted array into a height-balanced BST. Workday uses this for divide-and-conquer tree construction — same shape as building a balanced compensation-band tree from sorted salary ranges.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

Problem

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

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]

Example 2

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

Approaches

1. Greedy insertion

Insert each element into a BST.

Time
O(n^2) worst case
Space
O(n)
// inserting into a BST one at a time — produces a skewed tree from sorted input

Tradeoff: From sorted input, naive insertion produces a degenerate tree.

2. Recursive midpoint selection

Pick the middle element as the root. Recurse on left half (left subtree) and right half (right subtree).

Time
O(n)
Space
O(log n) stack)
function sortedArrayToBST(nums) {
  function build(left, right) {
    if (left > right) return null;
    const mid = (left + right) >>> 1;
    return {
      val: nums[mid],
      left: build(left, mid - 1),
      right: build(mid + 1, right)
    };
  }
  return build(0, nums.length - 1);
}

Tradeoff: Single recursion. The midpoint guarantees balance: each subtree has roughly half the elements.

Workday-specific tips

Workday wants the divide-and-conquer approach. State 'midpoint as root' before coding — that's the entire insight. Note that picking floor vs ceil mid produces different valid trees; both pass.

Common mistakes

  • Inserting one at a time from sorted input — produces a skewed tree.
  • Off-by-one on the recursive bounds.
  • Using slice instead of indices — wasteful allocations.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • Convert Sorted List to BST (LC 109).
  • From sorted-doubly-linked-list to BST.
  • What if balance constraint is stricter (AVL)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why midpoint balanced?

The midpoint splits the array in half — left subtree has floor((n-1)/2) elements, right has ceil((n-1)/2). Recurse with the same invariant, and depth differences stay within 1.

Floor or ceil mid?

Either. Both produce a valid balanced BST. The tree shape differs slightly, but both are valid answers.

Practice these live with InterviewChamp.AI

Drill Convert Sorted Array to Binary Search Tree and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →