Sorted array to a height-balanced BST

Why this matters

The previous lesson showed that sorted input makes a binary search tree into a chain. A chain of n keys has height n, so every search can cost n steps. You need a tree whose height stays small.

A sorted array is a good starting point. The middle element splits the keys into two halves that are each sorted, and each half can be split the same way. If you always pick the middle as the root, the two sides of the tree end up almost the same size. That gives a tree whose height is about the number of times you can halve n.

This lesson builds that tree, checks it with real output, and proves the height formula. It does not cover inserts after the build. Self-balancing trees for inserts come later in this module, in the AVL rotations and red-black tree lessons.

Height is counted in nodes. An empty tree has height 0, and a single node has height 1. The term log n means the logarithm of n in base 2, which is the number of times you can divide n by 2 before you reach 1. For example, log2 of 8 is 3, because 8 divided by 2 three times is 1.

The idea in plain words

Take the sorted array 1, 2, 3, 4, 5, 6, 7. The middle element is 4, at index 3. Make 4 the root.

The keys to the left of 4 are 1, 2, 3. Build a tree from them the same way. Their middle is 2, so 2 becomes the left child of 4. The keys 1 and 3 are then left and right of 2.

The keys to the right of 4 are 5, 6, 7. Their middle is 6. So 6 becomes the right child of 4, with 5 and 7 under it.

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

The tree is a valid binary search tree. Every key is larger than everything on its left and smaller than everything on its right. Its height is 3, and seven keys fit in height 3.

The rule has three parts, and each part is needed:

1. Pick the middle index of the range as the root.
2. Build the left side from the keys before the middle.
3. Build the right side from the keys after the middle.

Step 2 and step 3 are the same problem on a smaller range, so one recursive function does both.

Half-open ranges

The code uses a half-open range. The range [lo, hi) includes lo and stops before hi. So lo is the first index and hi is one past the last index. The range is empty when lo equals hi.

Half-open ranges avoid mistakes. The number of elements in [lo, hi) is hi - lo. An empty range has lo == hi, so the base case is a single check. The middle index is lo + (hi - lo) / 2. The left half is [lo, mid), which excludes the middle. The right half is [mid + 1, hi), which also excludes the middle.

Here is the function. It takes the sorted array and a range, and it returns the root of a new tree.

unique_ptr<Node> build(const vector<int>& a, int lo, int hi) {
    if (lo >= hi) return nullptr;
    int mid = lo + (hi - lo) / 2;
    auto node = make_unique<Node>(a[mid]);
    node->left = build(a, lo, mid);
    node->right = build(a, mid + 1, hi);
    return node;
}

The program below uses this function. It also prints the tree, checks that an in-order walk gives back the input, and checks the height formula for every size from 1 to 1,000.

An in-order walk visits the left subtree, then the node, then the right subtree. For a valid binary search tree, the keys come out in sorted order. If the walk gives back the input array, the tree holds the same keys in the right order.

The printed tree is sideways. The root is on the left edge, the right subtree is printed above it, and the left subtree is printed below it. Read it by tilting your head to the left.

The output from g++ 15 on Linux is below.

Tree from 1..7 (root at the left edge, right side printed on top):
        7
    6
        5
4
        3
    2
        1
in-order equals input: yes
height = 3
 
Height check, n from 1 to 1000:
height == bit_width(n) for every n: yes
 
    n   height   bit_width(n)   ceil(log2(n+1))
  1	1	1		1
  2	2	2		2
  3	2	2		2
  7	3	3		3
  8	4	4		4
  15	4	4		4
  16	5	5		5
  1000	10	10		10
  1000000	20	20		20

The in-order check says yes, so the tree holds the input in sorted order. The height is 3 for seven keys.

The check height == bit_width(n) passes for every n from 1 to 1,000. The function bit_width is a C++20 function in the <bit> header. The course runner compiles with C++17, so the program defines its own copy with the same result. It returns the number of bits needed to write n in binary. For n = 8 that is 4, because 8 is 1000 in binary. The part of this lesson called "Why the height is about log n" explains why this number is the height.

The last table compares the height with ceil(log2(n+1)), which is the smallest height any tree with n nodes can have. The two columns match in every row.

Why the height is about log n

This section proves the height formula. It has two parts: an upper bound from the build, and a lower bound that holds for every tree.

Step 1: the sizes of the two halves

Let the range hold n keys. So hi - lo = n. The middle is mid = lo + floor(n / 2), where floor means rounding down. The left half is [lo, mid), which has floor(n / 2) keys. The right half is [mid + 1, hi), which has n - floor(n / 2) - 1 keys. That number is at most floor(n / 2).

So both halves have at most floor(n / 2) keys. The left half is always the larger one, or equal in size.

Step 2: the height recurrence

The height of a node is one more than the larger of its children's heights. The larger child subtree has at most floor(n / 2) keys. Writing H(n) for the height of a tree built from n keys, this gives:

H(0) = 0, and H(n) = 1 + H(floor(n / 2)) for n of 1 or more.

Step 3: count the halvings

Each step of the recurrence replaces n by floor(n / 2). Here is the chain of values for n = 1000:

1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, 0

There are 10 steps before the value reaches 0. So H(1000) = 10. This matches the output.

In general, if 2^k <= n < 2^(k+1), then halving n a total of k+1 times reaches 0. So H(n) = k + 1. The number k is the position of the highest set bit in n, which is floor(log2 n). Therefore:

H(n) = floor(log2 n) + 1 = bit_width(n).

Check with a small case. For n = 7, the values are 7, 3, 1, 0, which is 3 steps. bit_width(7) is 3, because 7 is 111 in binary. For n = 8, the values are 8, 4, 2, 1, 0, which is 4 steps, and bit_width(8) is 4.

Step 4: no tree can do better

Now the lower bound. A binary tree of height h has at most 2^h - 1 nodes. On level 1 there is at most one node, on level 2 at most two, on level 3 at most four, and so on. Level i has at most 2^(i-1) nodes. Adding the levels from 1 to h gives 1 + 2 + 4 + ... + 2^(h-1), which equals 2^h - 1.

So a tree with n nodes needs 2^h - 1 >= n, which means h >= log2(n + 1). The smallest integer h that satisfies this is ceil(log2(n + 1)). The last column of the table shows this number, and our tree always matches it.

So the balanced build gives the smallest height that any tree with n nodes can have. The height is at most one more than log2 n, and that is what "height about log n" means.

What this means for searches

A search visits at most one node per level, so it visits at most H(n) nodes. For n = 1,000,000 the build gives height 20, so a search visits at most 20 nodes. The chain from the previous lesson would visit up to 1,000,000.

A second example with an even count

Now take an array with an even number of keys: 1, 2, 3, 4. The middle index is 0 + (4 - 0) / 2 = 2, so the root is a[2], which is 3. The left half is [0, 2), which holds 1 and 2. The right half is [3, 4), which holds 4.

Building the left half, the middle index is 0 + (2 - 0) / 2 = 1, so 2 becomes the left child of 3, and 1 goes under 2 as its left child. The right half has one key, 4, which is the right child of 3.

A preorder walk (root, then left subtree, then right subtree) of this tree prints 3, 2, 1, 4. This is the output from a test run with g++ 15:

preorder of 1..4 build: 3 2 1 4 
height 1..4: 3

The tree has height 3, which equals bit_width(4). Note that the left side got the extra key. When n is even, the left half has one more key than the right half.

A third example: the boundary cases

The formula gives a clear answer for sizes near powers of two. The sizes that have height 4 run from 8 to 15. Height 5 runs from 16 to 31. Height 6 starts at 32.

Here is a run with sizes 12, 31, and 32:

n=12 height=4
n=31 height=5
n=32 height=6

The output matches the formula. A tree of 31 keys is full, with all five levels filled, so no smaller height is possible. Adding one key, as in 32, forces a sixth level.

Watching the calls

To see the recursion at work, add one line of output to each call. The version below prints the range [lo, hi), the root it picks, and a line for each empty range. Indentation shows how deep the call is.

unique_ptr<Node> build(const vector<int>& a, int lo, int hi, int depth) {
    if (lo >= hi) {
        cout << string(depth * 2, ' ') << "build [" << lo << ", " << hi << ") -> empty\n";
        return nullptr;
    }
    int mid = lo + (hi - lo) / 2;
    cout << string(depth * 2, ' ') << "build [" << lo << ", " << hi << ") -> root " << a[mid]
         << " (index " << mid << ")\n";
    auto node = make_unique<Node>(a[mid]);
    node->left = build(a, lo, mid, depth + 1);
    node->right = build(a, mid + 1, hi, depth + 1);
    return node;
}

Called on 1 to 7 with build(a, 0, 7, 0), it prints this from g++ 15:

build [0, 7) -> root 4 (index 3)
  build [0, 3) -> root 2 (index 1)
    build [0, 1) -> root 1 (index 0)
      build [0, 0) -> empty
      build [1, 1) -> empty
    build [2, 3) -> root 3 (index 2)
      build [2, 2) -> empty
      build [3, 3) -> empty
  build [4, 7) -> root 6 (index 5)
    build [4, 5) -> root 5 (index 4)
      build [4, 4) -> empty
      build [5, 5) -> empty
    build [6, 7) -> root 7 (index 6)
      build [6, 6) -> empty
      build [7, 7) -> empty

Read the trace from the top. The first call covers all seven keys, so its root is index 3, which holds 4. The call for the left half, [0, 3), picks index 1, which holds 2. Each call prints its line before it makes its child calls, so the lines appear in the order the calls start.

Every non-empty range prints exactly one root line. There are seven root lines, one for each key: 4, 2, 1, 3, 6, 5, 7. No key is left out and none is used twice. The empty lines are the ends of the recursion, and there is one for each missing child.

A worked example with five keys

An odd count shows the rule in a different way. Take the sorted keys 10, 20, 30, 40, 50 and call build(b, 0, 5, 0). The first call covers five keys, and its middle index is 0 + 5 / 2 = 2, so the root is 30.

The left half is indices 0 and 1, which hold 10 and 20. Its middle index is 0 + 2 / 2 = 1, so its root is 20, and 10 is the left child of 20. The right half is indices 3 and 4, which hold 40 and 50. Its middle index is 3 + 2 / 2 = 4, so its root is 50, and 40 is the left child of 50.

Both halves have two keys. The left half has floor(5 / 2) = 2 keys, and the right half has 5 - 2 - 1 = 2 keys, as the proof says. The height is 3, which matches bit_width(5), because 5 is 101 in binary.

The root is not the middle value 30 by accident. It is the element at index 2 of the sorted array. For an odd count, the middle element is the median, the value with the same number of keys below it and above it.

Common mistakes

Mixing up the end index

The most common bug is to use an inclusive end index in one place and an exclusive one in another. Here is a version that uses inclusive ends [lo, hi], and passes mid instead of mid + 1 for the right half:

unique_ptr<Node> build_bug(const vector<int>& a, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = (lo + hi) / 2;
    auto node = make_unique<Node>(a[mid]);
    node->left = build_bug(a, lo, mid - 1);
    node->right = build_bug(a, mid, hi);
    return node;
}

When the range has one key, lo equals hi and mid equals lo. The right call is build_bug(a, mid, hi), which is the same range as before. The function calls itself with the same arguments forever, until the call stack runs out.

Calling it on the keys 1 to 7 crashes the program, and the shell reports the exit code:

exit code: 139

Exit code 139 means the process was killed by a segmentation fault, which is a crash caused by using memory the program may not touch. Here the crash comes from the call stack running out of space.

The rule to remember: pick one convention and write it in a comment at the top of the function. The lesson's version uses [lo, hi) and passes mid + 1 to the right half.

Passing the unsorted array

The build depends on the input being sorted. If the array is not sorted, the tree is still built, but its in-order walk will not be sorted. The in-order check in the program is a good test to run after every build. It costs O(n) time and catches this mistake at once.

Overflow in the middle formula

The formula (lo + hi) / 2 can overflow an int when both indices are large. The form lo + (hi - lo) / 2 never adds two large numbers, so it is safe. The lesson uses that form.

Practice

Exercise 1. Build a tree from the sorted array 1, 2, 3, 4 with the rule in this lesson. What is the root, and what is the height?

Show the answer

The root is 3, which is a[2]. The height is 3. The preorder walk prints 3, 2, 1, 4.

Exercise 2. What is the height of a balanced tree with 12 keys? Give your reason using bit_width.

Show the answer

The height is 4. bit_width(12) is 4, because 12 is 1100 in binary, which has four bits. Halving 12 gives 6, 3, 1, 0, which is four steps.

Exercise 3. What is the largest number of keys that fits in a balanced tree of height 5? What is the smallest number of keys that needs height 6?

Show the answer

The largest is 31, because height 5 holds at most 2^5 - 1 = 31 nodes. The smallest is 32, because 32 has bit_width 6. The output above shows height 5 for 31 keys and height 6 for 32 keys.

Exercise 4. Explain why the body of build uses mid + 1 for the start of the right half and mid for the end of the left half.

Show the answer

The middle key a[mid] is the root, so it must not appear in either half. The left half is [lo, mid), which stops before mid. The right half is [mid + 1, hi), which starts after mid. If the right half started at mid, the root would appear again in its own subtree.

Exercise 5. Estimate the height of a balanced tree with one billion keys. Use the formula, then check it against the table in the lesson.

Show the answer

The height is bit_width(1000000000). Two to the power 29 is 536,870,912, and 2 to the power 30 is 1,073,741,824. One billion lies between them, so its highest set bit is at position 29, and the height is 30. A search needs at most 30 steps. A chain of one billion keys would need up to one billion steps.

Summary

• The middle element of a sorted range becomes the root, and each half is built the same way.
• Half-open ranges [lo, hi) keep the base case and the middle formula simple.
• The height of this tree is bit_width(n), which is floor(log2 n) + 1, because each level halves the number of keys.
• No binary tree with n nodes can have a smaller height than ceil(log2(n + 1)), so the build is optimal for height.
• A build from a sorted array does not handle later inserts, which need a self-balancing tree.