Free Trees lessonsTrees · Stage 4 · Building and comparing · Step 2

A balanced tree from a sorted list

Turn a sorted array into a search tree of minimal height, by making the middle value the root and building each side from the half that lies on that side. About 14 minutes.

The middle becomes the root

In a search tree, everything in the left subtree is smaller than the root, and everything in the right subtree is larger. A sorted array already has smaller values on the left of any position and larger ones on the right.

So pick the middle position as the root. Everything before it forms the left subtree, and everything after it forms the right one. Build each half in the same way.

Middle: of the range becomes the root.

Each half: is built the same way.

In code

mid = (lo + hi) // 2
node = TreeNode(nums[mid])

Build from the sorted values 1, 3, 4, 6, 8, 9.

left: [1, 3]
right: [6, 8, 9]

The six values have two middles. Take the left one, 4. It becomes the root. 1 and 3 are left of it, 6, 8 and 9 are right.

Move 1 of 4

Ranges, and which middle

Describe each piece by a range of positions, lo to hi. An empty range, where lo is above hi, gives no node, and that ends the recursion.

When a range has an even number of values, there are two middles. This task takes the left one, by rounding down when halving. That makes the tree unique, so answers can be compared. The two sides never differ in size by more than one.

Even range: choose the left middle, rounding down.

lo above hi: means no node.

In code

size = hi - lo + 1     # 0 means: no node

Quick check

Why pick the middle value as the root, rather than the first?

AIt splits the values evenly, so the tree has the smallest possible height
BIt keeps the array sorted
CSmaller roots make smaller trees

Show the answer

It splits the values evenly, so the tree has the smallest possible height. Both sides get about half of the values, and the same rule is used in each half.

Your problem

Convert sorted array to height-balanced BST

Given an integer array nums sorted in increasing order, build a height-balanced binary search tree from it and return its root. When a range has two middle elements, use the left one (the element at position (lo + hi) divided by 2, rounded down), so that the answer is unique.

Example

nums = [-10, -3, 0, 5, 9] → [0, -10, 5, null, -3, null, 9]

0 ≤ length of nums ≤ 10,000 · nums is sorted in increasing order, with different values

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.