Skip to main content

65. Convert Sorted Array to Binary Search Tree

easyAsked at Datadog

Convert a sorted array into a height-balanced BST. Datadog uses this for the recursive midpoint split — same pattern they use when bulk-loading an ordered chunk into a balanced index tree.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — bulk-load analog.

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] or [0,-10,5,null,-3,null,9]

Example 2

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

Approaches

1. Insert one by one

Iterate nums; insert each into a growing BST.

Time
O(n^2) worst case
Space
O(n)
// Insert each value with standard BST insert; produces a SKEWED tree (degenerate) because the input is already sorted.

Tradeoff: Degenerate balance. Datadog will fail you for not exploiting sortedness.

2. Recursive midpoint split (optimal)

Recurse on [lo, hi]. Pick mid = (lo + hi) >>> 1 as root. Recurse on [lo, mid-1] and [mid+1, hi].

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

Tradeoff: O(n) construction, balanced output. Datadog-canonical: identical to bulk-loading a sorted run into a balanced B-tree segment.

Datadog-specific tips

Datadog grades on whether you spot the divide-and-conquer immediately. The middle-as-root choice GUARANTEES balance because the two halves are within one of each other in size. Articulate this before coding.

Common mistakes

  • Using (lo + hi) / 2 with floating-point semantics in JS — use (lo + hi) >>> 1 or Math.floor.
  • Recursing on overlapping ranges — duplicates the mid in either half.
  • Trying to balance after insertion — you'd need AVL/red-black rotations, which is overkill here.

Follow-up questions

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

  • Convert Sorted List to BST (LC 109) — same idea but on a linked list (O(n) total).
  • Datadog-style: bulk-load a sorted run into a balanced index tree.
  • Balanced BST query — verify height invariant after construction.

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 does the midpoint split balance the tree?

Each subtree has half the array; the height recurrence is T(n) = T(n/2) + 1, giving O(log n) height — balanced.

Multiple valid answers?

Yes — left-mid vs right-mid both produce valid balanced BSTs. The problem accepts either.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →