Sorted list to a height-balanced BST in Python

Why this matters

The previous lesson showed that inserting sorted values one at a time gives a tree that is a chain. A chain of n values has height n, so a search can take n steps. The data was sorted, and sorted data is common. Records are often stored by ID or by date, and a list you receive from a file or a database is often already in order.

This lesson shows a different way to build the tree. You do not insert values one at a time. You look at the whole sorted list at once, pick the middle value as the root, and build the left and right halves the same way. The result is a tree whose height is about log n, no matter how many values there are.

The lesson stays on this one build method. Keeping a tree balanced while values arrive one at a time is the job of the AVL and red-black lessons later in this module. The previous lesson, "Why sorted input makes a Python BST a chain", explains why the naive insert fails.

Words used in this lesson

A sorted list is a Python list of values in increasing order. Index 0 is the first value, index 1 is the second, and so on up to len(a) - 1.

A height-balanced tree is a tree where, at every node, the left subtree and the right subtree have heights that differ by at most 1. You will see this definition again in the AVL lesson.

The middle of a range of indexes is the index halfway between the first and last index. For indexes lo to hi, the middle is lo + (hi - lo) // 2. The // operator divides and drops the fraction, so for an even count the middle is the lower of the two central positions.

A range here means the part of the list from index lo to index hi, both included.

log n means the logarithm of n in base 2, written log2 n. It is the number of times you can cut n in half before you reach 1. For n = 8, log2 8 = 3, because 8 becomes 4, then 2, then 1 in three halvings.

The idea in one sentence

Pick the middle value of the sorted list as the root. Everything to its left in the list is smaller, so it goes in the left subtree. Everything to its right is larger, so it goes in the right subtree. Build each half with the same rule.

The sorted order does the work for you. Because the list is sorted, the values left of the middle are all smaller than the middle, and the values right of the middle are all larger. The BST rule holds at the root without any comparisons.

Worked example 1: seven values

Take this sorted list, with indexes 0 to 6:

index:  0    1    2    3    4    5    6
value: 10   20   30   40   50   60   70

Step 1. The range is indexes 0 to 6. The middle is 0 + (6 - 0) // 2 = 3. The value at index 3 is 40. Make 40 the root.

Step 2. The left half is indexes 0 to 2, which holds 10, 20, 30. Build a tree from this range. The middle is 0 + (2 - 0) // 2 = 1. The value at index 1 is 20. Make 20 the left child of 40. Then the left half of this range is index 0 alone, which holds 10. Make 10 the left child of 20. The range to the right of index 1 is index 2 alone, which holds 30. Make 30 the right child of 20.

Step 3. The right half is indexes 4 to 6, which holds 50, 60, 70. The middle is 4 + (6 - 4) // 2 = 5. The value at index 5 is 60. Make 60 the right child of 40. Then 50 becomes the left child of 60, and 70 becomes the right child of 60.

The finished tree looks like this:

            40
          /    \
        20      60
       / \     / \
      10  30  50  70

Count the levels. There are three: 40 alone, then 20 and 60, then the four leaves. The height is 3. The seven values fit in three levels, which is the smallest height any tree of seven nodes can have.

The code

The program below builds the tree from a sorted list. The function build takes the list and a range, lo and hi. If the range is empty, lo is greater than hi, and it returns None. Otherwise it picks the middle, makes a node from that value, and builds the left and right halves.

The real output is:

Seven values, tree sideways:
        70
    60
        50
40
        30
    20
        10
root = 40, height = 3
inorder walk = [10, 20, 30, 40, 50, 60, 70]
 
n, height, ceil(log2(n+1)), inorder matches input
1, 1, 1, True
2, 2, 2, True
3, 2, 2, True
7, 3, 3, True
8, 4, 4, True
15, 4, 4, True
16, 5, 5, True
100, 7, 7, True
1000, 10, 10, True
10000, 14, 14, True
 
n=1000000 height=20 ceil(log2(n+1))=20

The sideways picture is the same reading rule as the previous lesson. The root, 40, is the line with no indent. Each level down adds four spaces, and the right child is printed above its parent. Compare it with the diagram from the worked example: the same values, drawn on their side.

The inorder function visits the left subtree, then the node, then the right subtree. The inorder walk prints [10, 20, 30, 40, 50, 60, 70], which is the original list. This is a useful check. If the walk does not give back the input in order, the tree is not a valid BST.

The last value on each line, True, is shown for every size. The tree holds exactly the values from the list, in the same order. The check out == a compares two lists item by item, so one comparison covers all the values.

Worked example 2: an even number of values

The worked example above had seven values, which splits evenly. An even count needs a rule for the middle. Take four values:

index:  0   1   2   3
value:  1   2   3   4

The range is 0 to 3. The middle is 0 + (3 - 0) // 2. The // operator drops the fraction, so 3 // 2 is 1. The middle index is 1, and the root is 2.

The left half is indexes 0 to 0, which holds only 1. That is a leaf. The right half is indexes 2 to 3, which holds 3 and 4. Its middle is 2 + (3 - 2) // 2 = 2 + 0 = 2. The value at index 2 is 3, which becomes the root of this half. The value 4 is its right child.

The result is root 2, left child 1, right child 3, and then 4 under 3 on the right. The height is 3.

Here is the tree for the values 1 to 4. Calling print_sideways on build_from_sorted([1, 2, 3, 4]) prints:

        4
    3
2
    1

The tree has four values and height 3. For four values, 2 levels would hold at most 3 nodes, so 3 is the smallest height possible. The rule of taking the lower middle was a choice. Taking the upper middle would also work, and it would give a tree of the same height here. The rule only needs to be the same at every step.

Worked example 3: a bigger tree and the height rule

Now try 1,000,000 values. The program above builds this tree and reports a height of 20. You can check the number without running anything.

Each time the range is split, the number of values in each half is at most half of the range, rounded down. Start with n values. The root takes one. The two halves hold together n minus 1 values, and each half holds at most half of n.

Follow this down the levels. After one split, each subtree holds at most n / 2 values. After two splits, at most n / 4. After k splits, at most n / 2 to the power k. A subtree that is empty is not a level, so the tree stops growing once the subtrees hold less than one value.

The height is the number of levels that hold at least one value. The last level that has a value is the level where n / 2 to the power k is at least 1. That happens when 2 to the power k is at most n, so k is at most log2 n. So the number of levels is at most log2 n plus 1, which is floor(log2 n) + 1.

For n = 1,000,000, log2 n is about 19.93. The floor, which means rounding down, is 19, and 19 + 1 = 20. The program printed 20.

The same number can be written as ceil(log2(n + 1)), where ceil means rounding up. This is the value the program prints in its third column. For every n in the table, the height matches it. For n = 8, floor(log2 8) + 1 = 4, and ceil(log2 9) = 4. For n = 7, floor(log2 7) + 1 = 3, and ceil(log2 8) = 3.

The key fact is this. The height grows with log n, not with n. Going from 1,000 values to 1,000,000 values, n grows a thousand times, but the height only grows from 10 to 20.

What the height means for a search

A search walks down one path from the root. At each node it makes one comparison and goes left or right. So the number of comparisons for a search is at most the height.

For the 1,000,000 value tree, a search takes at most 20 comparisons. For the chain built from the same sorted values in the previous lesson, a search could take up to 1,000,000. The build function in this lesson changes the cost from a million steps to twenty steps, without changing the data or the order it arrives in.

The cost of building the tree is also small. The build function visits each value once, and it does a fixed amount of work at each node, so building takes time proportional to n. Compare this with the insert from the previous lesson, which took about n * (n - 1) / 2 comparisons for sorted input.

Common mistakes

The input is not sorted

The build function assumes the list is sorted in increasing order. If it is not, the tree will break the BST rule, and the search will return wrong answers. Check the result with the inorder walk. If the walk does not print the values in order, the input was not sorted.

For example, with the list [30, 10, 20] the root is 10, the left child is 30, and the right child is 20. A search for 20 starts at 10, goes right, and finds 20. A search for 30 starts at 10, sees that 30 is larger, and goes right to 20. It never looks at the left child of 10, where 30 sits, so the search reports that 30 is missing. The tree is wrong, and the program did not crash, so the bug is quiet.

The recursion range is wrong at one end

The most common error is a wrong end index in one of the recursive calls. The two versions below were both run on the list [1, 2, 3].

The first version uses the same range for the left half as the parent, by passing mid instead of mid - 1 as the end:

node.left = build(a, lo, mid)

When the range is 0 to 1, the middle is 0, and the left half is 0 to 0, which is the same range again. The call repeats forever until the call stack is full. The program stops with this message:

RecursionError: maximum recursion depth exceeded

The fix is to exclude the middle from the left half, with mid - 1, as the program above does.

The second version starts with the wrong end of the whole list, by calling build(a, 0, len(a)) instead of build(a, 0, len(a) - 1) in build_from_sorted. The end index is one past the last valid index. The program reads a value that does not exist:

return build(a, 0, len(a))

The message, with the list [1, 2, 3], is:

IndexError: list index out of range

The valid indexes are 0, 1 and 2, and the call asked for index 3. The traceback above the message shows the line where a[mid] was read.

Stopping after one level

Some people build the root and then the two halves, and stop there, because the code looks like it works for seven values. Each half must be built with the same rule, recursively, until the range is empty. Stopping early makes a tree whose height is 2 for seven values, and it leaves values out. The inorder walk shows the missing values.

Copying slices instead of passing indexes

A common alternative is to pass slices of the list, such as a[:mid] and a[mid + 1:]. Slices are easy to read, and they give the same tree. Each slice makes a new list, though, so building a tree of n values copies about n times log n items in total, instead of passing the same list with two indexes. For small lists the difference does not matter. For a million values the index version is the better habit.

The middle formula in other languages

The formula lo + (hi - lo) // 2 avoids a problem that (lo + hi) // 2 can have in languages with fixed-size integers. There, lo + hi can be larger than the largest value the integer type can hold, and the sum wraps around to a negative number, so the middle index is wrong. The form lo + (hi - lo) // 2 never goes above hi, so it is safe in every language. Python integers have no fixed size limit, so (lo + hi) // 2 would also work here. Use the safe form anyway, so that the same habit carries over to other languages.

Practice

Exercise 1

Build the tree from the sorted list [1, 2, 3, 4, 5, 6] using the rule from this lesson. What is the root? What are the children of the root? What is the height?

Show the answer

The range is indexes 0 to 5, and the middle is 0 + 5 // 2 = 2. The root is the value at index 2, which is 3. The left half is 1 and 2. Its middle is 0 + 1 // 2 = 0, so 1 is the left child of 3, and 2 is the right child of 1. The right half is 4, 5 and 6. Its middle is 3 + 2 // 2 = 4, so 5 is the right child of 3, with 4 on its left and 6 on its right. The root's children are 1 (left) and 5 (right). The height is 3. To check, build the tree from these values with build_from_sorted and print it with print_sideways. You should see root 3, left child 1 with right child 2, and right child 5 with children 4 and 6.

Exercise 2

For a sorted list of 10 values, what is the height of the tree built by this method? Work it out with the formula, then check it with the code.

Show the answer

The height is floor(log2 10) + 1. Since log2 10 is about 3.32, the floor is 3, and 3 + 1 = 4. Building the tree from the values 1 to 10 gives root 5 and height 4, which matches.

Exercise 3

A sorted list has 1,000,000 values. A second sorted list has 2,000,000 values. How much taller is the second tree? Give the answer as a number of levels.

Show the answer

The second tree is about one level taller. Doubling n adds one to log2 n, so the height goes from floor(log2 1000000) + 1 = 20 to floor(log2 2000000) + 1 = 21. Doubling the size of the data adds one level to the tree.

Exercise 4

The code below is meant to build a tree from a sorted list, but it has a bug. Find the line that is wrong and say what the program prints when it runs.

def build(a, lo, hi):
    if lo > hi:
        return None
    mid = lo + (hi - lo) // 2
    node = Node(a[mid])
    node.left = build(a, lo, mid)
    node.right = build(a, mid + 1, hi)
    return node

Show the answer

The bug is node.left = build(a, lo, mid). The left half should end at mid - 1, because mid is already the root. Once the range is down to one value, lo and mid are the same index, so the left call builds that same one-value range again and never stops. The program fails with RecursionError: maximum recursion depth exceeded, and the traceback shows the function build on many lines.

Exercise 5

Explain in your own words why the inorder walk of the built tree returns the original sorted list. Use the words left, node and right in your answer.

Show the answer

The inorder walk visits the left subtree, then the node, then the right subtree. For each node made by the build function, the left subtree holds the values with smaller indexes, the node holds the middle value, and the right subtree holds the values with larger indexes. Following the walk visits indexes in increasing order, so the output is the original list.

Summary

• Build a tree from a sorted list by making the middle value the root and building the left and right halves with the same rule.
• Use lo + (hi - lo) // 2 for the middle, and check that the recursion ends at lo > hi.
• The height is floor(log2 n) + 1, so a tree of 1,000,000 values has height 20.
• A search in this tree takes at most its height in comparisons, so it is far faster than the chain from the previous lesson.
• The inorder walk gives back the input when the tree is built correctly, which makes a useful check.
• This method needs the data in sorted order before the build. For values that arrive one at a time, use a self-balancing tree from later in this module.