Why sorted input makes a Python BST a chain

Why this matters

A binary search tree (BST) is meant to find a value fast. Each node has at most two children, a left child and a right child. Every value in the left subtree is smaller than the node, and every value in the right subtree is larger. Searching means starting at the root and going left or right at each node, so each step throws away about half of the tree.

That speed depends on the tree being short and wide. The shape depends on the order in which you inserted the values. If you insert values in sorted order, the tree becomes a straight line. A line is the worst possible shape for a BST, and the search becomes as slow as checking a plain list one item at a time.

This lesson shows the problem with real code, counts the work it costs, and shows the two common ways to avoid it. The next lesson builds a short tree from a sorted list, and the AVL and red-black lessons later in this module keep a tree short while values are inserted one at a time.

Words used in this lesson

A node is one box in the tree. It holds a value and two links, left and right. A link can be None, which means there is no child there.

The root is the top node, the one with no parent.

A leaf is a node with no children.

The height of a tree is the number of nodes on the longest path from the root down to a leaf. A tree with one node has height 1. An empty tree has height 0.

A chain is a tree where every node has at most one child. Its height equals the number of nodes.

A comparison is one check of the form "is the new value smaller than this node's value?" Each comparison costs a little time, so the number of comparisons is a good measure of how much work an insert or a search does.

A small example by hand

Start with an empty tree and insert 1, then 2, then 3.

Insert 1. The tree is empty, so 1 becomes the root.

1

Insert 2. Start at the root, which is 1. Two is larger than 1, so go right. The right link of 1 is empty, so 2 goes there.

1
 \
  2

Insert 3. Start at the root, 1. Three is larger than 1, so go right. The node there is 2. Three is larger than 2, so go right. The right link of 2 is empty, so 3 goes there.

1
 \
  2
   \
    3

The tree now has three levels, so its height is 3. Notice what happened. Each new value was larger than everything before it, so each one went right, under the value just inserted. No value ever went left. The tree is a chain.

If you insert 4 and 5 the same way, the height becomes 5. In general, n sorted values inserted in increasing order give a tree of height n.

The code

The program below builds the tree in Python. It uses a Node class with a value and two child links, an insert function that walks down with a loop, a height function, and a counter that counts comparisons. Save it as chain_demo.py.

The insert uses a loop instead of recursion. The reason is explained in the common mistakes section. Python stops a chain of nested calls at about 1000 calls by default, and a sorted run of 5000 values would go that deep if the insert called itself for each level.

The real output is:

Sorted input 1..5, tree sideways (root at left):
                5
            4
        3
    2
1
height = 5
 
Sorted input, size, height, comparisons:
n=10 height=10 comparisons=45
n=100 height=100 comparisons=4950
n=1000 height=1000 comparisons=499500
n=5000 height=5000 comparisons=12497500
 
Same values, shuffled with Random(42), size, height, comparisons:
n=10 height=5 comparisons=21
n=100 height=11 comparisons=618
n=1000 height=21 comparisons=11151
n=5000 height=29 comparisons=72212

The sideways picture is a way to read the tree on screen. Turn your head to the left. The root is the line with no indent, and in this picture it is the bottom line. Each level down the tree adds four spaces. The right child of a node is printed above it, and the left child is printed below it. For the sorted input, the picture is a diagonal staircase: each value sits one step further in than the one before it.

The shuffled rows use random.Random(42).shuffle, which is Python's seeded shuffle. A different Python version or a different shuffle function gives different numbers, so your own run may show other heights and counts for the shuffled rows. The sorted rows do not depend on the shuffle, so they match on every run.

Reading the first result

The first block of output is the picture for the values 1 to 5. Read it from the bottom. The root is 1, which has no left child. Its right child is 2, and so on up to 5. The height is 5, matching the hand example.

Now look at the sorted runs. For n=10 the height is 10, for n=100 it is 100, and for n=5000 it is 5000. In every case the height equals n. That is the chain.

Counting the work

The counter comparisons shows how much work the inserts did. For sorted input the count is large. When the value with position k is inserted, the tree already holds k minus 1 values, all smaller. The new value is larger than every one of them, so the insert walks down the whole chain and makes one comparison per node it passes. The insert for position k makes k minus 1 comparisons.

Add them up for all n values:

0 + 1 + 2 + ... + (n - 1) = n * (n - 1) / 2

Check it against the output. For n=10, that is 10 * 9 / 2 = 45, which matches. For n=100, it is 100 * 99 / 2 = 4950, which matches. For n=1000 it is 499500, and for n=5000 it is 12497500. The work grows with the square of n. Doubling the input makes the work about four times larger.

A balanced tree does far less work. A good tree of n values has height about log2 n, where log2 n is the number of times you can halve n before reaching 1. For n=1000 that is about 10, so each insert makes about 10 comparisons. The chain makes about 500 on average. The next section shows the same values inserted in a random order.

The same values in a random order

The second part of the program takes the same numbers and shuffles them. The seed random.Random(42) makes the shuffle repeatable, so you get the same output every time you run it. The order is no longer sorted, so the values do not all fall to the right of the one before.

For n=1000 the shuffled run in the output has a height of 21 and 11151 comparisons. The height dropped from 1000 to 21, and the work dropped from 499500 comparisons to about 11151.

Look at the shuffled height for n=10, which is 5, and for n=5000, which is 29. These are not the best possible heights, but they are far below n. A random order does not guarantee a short tree. It makes a long chain very unlikely. For random input, the height of a BST grows like a small multiple of log n, not like n.

Worked example: a log of events in time order

Suppose a program stores one record for each event in a log, keyed by a timestamp such as 1, 2, 3, and so on. Each new event has a later timestamp than all the events before it. The program inserts them in the order they arrive, which is also sorted order.

After 1,000 events, the tree is a chain of 1,000 nodes. Looking up one event costs up to 1,000 comparisons. The lookup gets slower with every event the program records, because the chain gets longer.

If the same 1,000 events went into a balanced tree instead, a lookup would cost about 10 comparisons. With a million events, a chain costs up to a million comparisons per lookup. A balanced tree costs about 20. The gap grows with the size of the data, which is why the shape of the tree matters.

Here is a rough table for the number of comparisons needed to find one value in the worst case. The chain column is n. The balanced column is about log2 n, rounded up.

Avoiding the chain

There are three practical ways to keep the tree short.

The first way is to change the input order. If the values can be shuffled before insertion, the tree will usually be short. This is the approach the second part of the program uses. It is simple, but it has a weak point. Shuffling is a guess about the input. A random order is very unlikely to make a chain, but no shuffle makes a chain impossible. Also, the data often arrives sorted for a reason, such as timestamps, and you may not control the order at all.

The second way is to build the tree from a sorted list without inserting one value at a time. You pick the middle value as the root and build the left and right halves the same way. This gives a tree whose height is about log n no matter how the values were sorted. It is the subject of the next lesson, "Sorted list to a height-balanced BST in Python".

The third way is to keep the tree balanced while values arrive one at a time. Self-balancing trees such as AVL trees and red-black trees do small repairs after an insert, called rotations, that keep the height close to log n. The AVL rotations lesson and the red-black tree lesson in this module cover these.

Common mistakes

Judging the shape from a small test

For small inputs, a chain and a balanced tree can look alike. Five sorted values give height 5, and five values in a good order give height 3. The gap is clear only when n grows. Do not conclude that the tree is fine because the test data is small.

Thinking a shuffle always fixes the problem

A random shuffle makes a chain very unlikely, but it does not promise a short tree. If you need a guaranteed height, use the build method from the next lesson or a self-balancing tree.

Running out of calls on a long chain

A recursive insert calls itself once for each level of the tree. Python keeps a record of each waiting call, and it stops with an error when more than about 1000 calls wait at once. The sorted values are the worst case, because the calls go one level deeper for every value.

Here is a recursive insert, with the same node class, that inserts the values 1 to 10000 in order:

def insert_rec(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert_rec(root.left, value)
    elif value > root.value:
        root.right = insert_rec(root.right, value)
    return root
 
 
root = None
for v in range(1, 10001):
    root = insert_rec(root, v)
print("inserted 10000 sorted values")

The program stops with this message at the end of a long trace:

RecursionError: maximum recursion depth exceeded

The trace shows the same line many times, because each line is one waiting call. The number of calls that fit depends on the Python version and the size of each call, so a different machine may fail at a different size. This lesson's demo uses a loop for insert, which does not add a call for each level, so it handles 5000 sorted values without an error. The loop version is also the better habit for trees that may become chains. A function that must recurse on a chain needs a loop, or a higher limit set with sys.setrecursionlimit, a function that changes the limit. Raising the limit only moves the point where the program stops.

Confusing the input order with the tree shape

The tree shape depends only on the order of the insert calls, not on the values themselves. Inserting 1, 2, 3 and inserting 5, 6, 7 produce chains of the same shape. Inserting 2, 1, 3 produces a balanced tree of three nodes. If you want to change the shape, change the order of the inserts or the way the tree is built.

Practice

Exercise 1

Insert the values 3, 1, 2 into an empty BST, in that order. What is the root, and what is the height?

Show the answer

The root is 3, because it is inserted first. The value 1 is smaller than 3, so it goes to the left of 3. The value 2 is smaller than 3, so it goes left, then it is larger than 1, so it goes to the right of 1. The height is 3. Every node has at most one child, so this tree is a chain, and its height equals n.

Exercise 2

Insert the values 4, 2, 6, 1, 3, 5, 7, in that order. What is the height?

Show the answer

The root is 4. The value 2 goes left of 4, and 6 goes right of 4. The values 1 and 3 go under 2, and 5 and 7 go under 6. Every leaf is at depth 3, so the height is 3. This tree holds 7 values in height 3, which is the smallest height any tree of 7 values can have.

Exercise 3

How many comparisons does inserting the values 1 to 20, in sorted order, make in total? Use the formula from this lesson. Then check your answer by running build_from(range(1, 21)) and printing comparisons.

Show the answer

The formula is n * (n - 1) / 2 with n = 20. That gives 20 * 19 / 2 = 190. Running the code with build_from on the values 1 to 20 prints 190 for the comparison count, and the height is 20.

Exercise 4

Write the values 5, 1, 4, 2, 3, in that order, as a tree. Which node is the root, which is the left child of the root, and what is the height?

Show the answer

The root is 5. The value 1 is smaller than 5, so it goes left. The value 4 is smaller than 5, so it goes left, then larger than 1, so it goes to the right of 1. The value 2 goes left of 5, then right of 1, then left of 4. The value 3 goes left of 5, right of 1, left of 4, then right of 2. The left child of the root is 1. The height is 5. Every node has at most one child, so the tree is a chain, and every value adds one level.

Exercise 5

A friend says that shuffling the input means the BST will always have height about log n. Is the claim correct? Explain with the numbers from this lesson.

Show the answer

The claim is not correct as stated. Shuffling makes a long chain unlikely, and the shuffled runs in this lesson had heights of 5, 11, 21 and 29, far below n. But the shuffle is random, so the height changes from run to run, and a particular unlucky order can still produce a tall tree. Shuffling is a good practical fix, not a guarantee. The sorted build in the next lesson gives a guaranteed height of about log n.

Summary

• Inserting sorted values into a BST makes every new value go to the right of the one before, so the tree becomes a chain of height n.
• A chain of n values needs n * (n - 1) / 2 comparisons to build, which grows with the square of n.
• A balanced tree of n values has height about log2 n, so a lookup needs about that many comparisons.
• Shuffling the input usually gives a short tree, but it is a guess, not a guarantee.
• A recursive insert can stop with a RecursionError when the chain is long enough. A loop avoids the problem.
• Building from a sorted list (next lesson) or using a self-balancing tree (AVL and red-black, later in this module) keeps the height short for sorted data.