Balanced Tree From Sorted Prices

EasyTrees

Problem

You receive a strictly increasing array nums and must load it into a height-balanced binary search tree so that later lookups are fast.

Build it deterministically: the root of every range nums[lo..hi] is the element at index (lo + hi) // 2 (integer division, so the left of the two middles when the range has even length). The elements before it form the left subtree and the elements after it the right subtree, built by the same rule. Return the root.

Example 1

Input:
nums = [1, 2, 3, 4, 5]
Output:
[3, 1, 4, null, 2, null, 5]

Root 3; [1, 2] picks index 0 → 1 with right child 2; [4, 5] picks 4 with right child 5.

Example 2

Input:
nums = [-10, -3, 0, 5, 9]
Output:
[0, -10, 5, null, -3, null, 9]

Example 3

Input:
nums = [7]
Output:
[7]

Constraints

  • 0 ≤ nums.length ≤ 10^4
  • -10^4 ≤ nums[i] ≤ 10^4
  • nums is strictly increasing.

Hint

Show the first hint

Which element must be the root so that both sides have (almost) the same number of elements?

Walkthrough

How to approach it

01Clarify before coding

  • Which middle for even lengths? The left one, index (lo + hi) // 2, so the answer is unique.
  • Can the array be empty? Yes: return an empty tree.
  • Should I slice the array? Better to pass indices: slicing copies O(n) per level.

02Brute force

Insert the values one by one into an empty search tree.

Cost: O(n²) time, because sorted insertions produce a chain of height n: exactly the unbalanced tree we must avoid.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.