A price catalog lands as a sorted int[]. Lookups need a search tree so a range walk is cheap. The intern version inserted each value in array order into a BST. A dozen prices looked like a tree. A million strictly increasing prices became a right-linked list with tree-shaped rent.

The mid of each remaining slice is the root of that subtree. Left of mid is smaller; right of mid is larger — that is the invariant Validate BST already checks with bounds. You are not hunting a target. You only take the mid of a sorted range so each cut is even. The array already gives nums[i]. The binary tree post owns shape. Here we only care about turning index bounds into nodes.

The problem

Given a strictly increasing sorted int[] nums, build a height-balanced binary search tree and return its root. At every node, left and right subtree heights differ by at most one. An empty array returns null. A single value is a one-node tree.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Walk nums = [-10, -3, 0, 5, 9]. Window [0, 4], mid index 2, so 0 is the root. Left window [-10, -3], right window [5, 9]. Floor-mid on a two-element window takes the left value as the parent and hangs the other as the right child:

      0
     / \
   -10  5
     \   \
     -3   9

Picking the other mid on even windows (-3 and 9 as parents) is also height-balanced. Both recover the array under inorder.

Note: Unique keys are the spec. A duplicate would need a side policy before you split; this prompt does not.

Sequential insert is the honest brute force

Start empty. Insert nums[0], then nums[1], … with ordinary BST insert. Correct search tree. Not balanced.

TreeNode sortedArrayToBSTSpine(int[] nums) {
    TreeNode root = null;
    for (int val : nums) {
        root = insert(root, val);
    }
    return root;
}

TreeNode insert(TreeNode node, int val) {
    if (node == null) {
        return new TreeNode(val);
    }
    if (val < node.val) {
        node.left = insert(node.left, val);
    } else {
        node.right = insert(node.right, val);
    }
    return node;
}

On a strictly increasing array every new key is larger than every ancestor, so every insert walks the current right spine and hangs a new right child:

-10
  \
  -3
    \
     0
      \
       5
        \
         9

Height n. Lookups O(n). The BST post already named this spine. A height-balanced answer is height Θ(log n).

Mid of the slice is the root

On window [lo, hi], if lo > hi return null. Else mid = lo + (hi - lo) / 2, allocate nums[mid], recurse on [lo, mid - 1] and [mid + 1, hi]. Same overflow-safe mid as binary search; there is no target comparison because the mid is this subtree’s root.

build(0, 4)  mid=2  root 0
  build(0, 1)  mid=0  node -10
    build(0, -1)  null
    build(1, 1)  mid=1  leaf -3
  build(3, 4)  mid=3  node 5
    build(3, 2)  null
    build(4, 4)  mid=4  leaf 9

The Java is that recurrence. Empty: first call is build(0, -1). One node: both child windows empty. No extra branch.

TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) {
        return null;
    }
    int mid = lo + (hi - lo) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, lo, mid - 1);
    root.right = build(nums, mid + 1, hi);
    return root;
}

Time is O(n) — each index becomes one node. Space is O(log n) frames because the tree, and the call tree, is balanced. Copying Arrays.copyOfRange at every split is extra allocations; the bounds are the window.

Do not search for a slot to insert nums[mid] into an already-built tree. The window already named the parent. Insert is how you grew the spine.

What interviewers usually poke next

  • The other even mid. mid = lo + (hi - lo + 1) / 2 still roots at 0, then parents -3 and 9 with left children -10 and 5. Also height-balanced; inorder still recovers nums. Name that both mids are accepted before you argue about which parent an even window picks.
  • Convert Sorted List to BST. Same idea, different mid: a list has no index. Slow-fast or an inorder-simulation build. Different prompt; do not convert the list to an array unless they allow the extra O(n) memory.
  • Prove it afterwards. Inorder must recover nums. Validate BST and a height-balance check are audits, not the construction.
  • Live inserts after the build. AVL / red-black keep the height under later writes. This prompt is a one-shot array. Do not rotate inside build.

You are done with this problem when you can draw [-10, -3, 0, 5, 9] from floor-mid, name the right spine sequential insert produces, and return null for an empty array without a special case.