Skip to main content

73. Convert Sorted Array to Binary Search Tree

easyAsked at Plaid

Convert a sorted array into a height-balanced BST. Plaid asks this because indexing a sorted financial-category list into a balanced lookup tree for O(log n) range queries is exactly the same primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid platform OA.
  • LeetCode Discuss (2026)— Plaid SWE II construction.

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]

Example 2

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

Approaches

1. Pick first element as root

Skewed tree — degenerate to a linked list.

Time
O(n)
Space
O(n)
// Skewed. Violates height-balanced requirement.

Tradeoff: Not balanced.

2. Pick middle as root, recurse

Middle of the array becomes the root. Left half becomes left subtree (recursively), right half becomes right subtree.

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

Tradeoff: Picking the middle guarantees the tree is height-balanced. Recursive stack is O(log n).

Plaid-specific tips

Plaid grades this on whether you realize the middle pick is the balanced choice. Bonus signal: discuss the variant where the array has duplicates — pick the leftmost middle or rightmost middle deterministically to keep the tree shape predictable.

Common mistakes

  • Picking lo as root — produces a right-skewed tree.
  • Using (lo + hi) / 2 without floor — produces a float index.
  • Returning a leaf for lo == hi but not handling lo > hi — null check is essential.

Follow-up questions

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

  • Convert a sorted linked list (LC 109) — in-order constructor pattern.
  • Same problem with duplicates allowed.
  • Convert to an AVL tree explicitly.

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 is the middle pick balanced?

Each recursive call halves the remaining range, so the resulting tree's depth is log2(n).

What if n is even — left or right middle?

Either gives a height-balanced tree; the LC test accepts both. Pick consistently to keep outputs deterministic.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →