65. Convert Sorted Array to Binary Search Tree
easyAsked at WorkdayConvert 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 Sam K., 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^4nums is sorted in a strictly increasing order.
Examples
Example 1
nums = [-10,-3,0,5,9][0,-3,9,-10,null,5]Example 2
nums = [1,3][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 inputTradeoff: 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.
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.