Why sorted input makes a BST a chain

Why this matters

A binary search tree is fast only while it is short. A search or an insert starts at the root and walks down one node at a time, so the number of steps equals the height of the tree, not the number of keys. A tree of 1,000 keys and height 10 needs at most 10 steps to find any key. The same 1,000 keys arranged in a line need up to 1,000 steps. A tree shaped like a line is called a chain, because it behaves like a linked list.

The order in which keys arrive decides the shape. The most common way to get a chain is to insert keys that already come in sorted order, such as IDs that go up by one each time or timestamps from a log. This lesson shows what happens, counts the steps, and then covers three ways to avoid the problem.

This lesson uses the insert and search rules from the first lesson of this module. It also uses the idea of height from the binary trees module. Height here is counted in nodes. An empty tree has height 0, and a single node has height 1.

The rule, briefly

Each node holds one key. Every key in the left subtree is smaller than the node's key, and every key in the right subtree is larger.

To insert a key, start at the root. If the new key is smaller than the current node's key, go left. Otherwise go right. When the next spot is empty, put the new node there.

Each node you look at on the way down costs one comparison. The number of comparisons for an insert is the number of nodes on the path before the new node is placed.

A tiny example by hand

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

1. Insert 1. The tree is empty, so 1 becomes the root. The path has 0 nodes, so 0 comparisons.
2. Insert 2. It is bigger than 1, so go right. The right spot is empty. The path has 1 node, so 1 comparison.
3. Insert 3. It is bigger than 1, so go right to 2. It is bigger than 2, so go right again. The spot is empty. The path has 2 nodes, so 2 comparisons.

The tree now looks like this:

1
 \
  2
   \
    3

The height is 3. Searching for 3 visits 1, then 2, then 3. No node can be skipped, because each new key went to the right of the last one.

This tree is still a valid binary search tree. Two is right of one, and three is right of two. The rule is not broken. The problem is the shape.

Ten sorted keys, step by step

The first program inserts the keys 1 to 10 in order. It counts the comparisons for each insert and prints the height at the end. Part 2 inserts the same ten keys in a mixed order. Part 3 compares sorted input with shuffled input for several sizes.

Here is the output from g++ 15 on Linux. The shuffled numbers depend on the shuffle code in the C++ standard library, so another library can print different shuffled numbers. The sorted numbers do not change.

Part 1: 1..10 inserted in sorted order
  insert 1 after 0 comparisons
  insert 2 after 1 comparisons
  insert 3 after 2 comparisons
  insert 4 after 3 comparisons
  insert 5 after 4 comparisons
  insert 6 after 5 comparisons
  insert 7 after 6 comparisons
  insert 8 after 7 comparisons
  insert 9 after 8 comparisons
  insert 10 after 9 comparisons
  height = 10, total comparisons = 45
 
Part 2: same 10 keys in a fixed mixed order
  height = 4, total comparisons = 19
 
Part 3: sizes n, sorted input vs shuffled input
     n  sorted_height  sorted_total_cmp  shuffled_height  shuffled_total_cmp
  10	10		45		6		25
  100	100		4950		15		661
  1000	1000		499500		22		11306
  2000	2000		1999000		24		24771

A few things to read from this output.

The line for insert 1 shows 0 comparisons because the tree is empty. Each later sorted insert makes one more comparison than the one before it. Insert 10 makes 9 comparisons, because the path goes through all nine earlier nodes.

The height is 10 for ten keys. Every node has only a right child, so the height equals the number of keys.

The unique_ptr type is a smart pointer. It owns the node it points to, and it frees that node when the owner goes away. make_unique builds a node and returns a unique_ptr to it. The program never calls delete.

The insert function does not use recursion. It keeps a pointer to the link that should receive the new node. The variable cur points at a unique_ptr, and that unique_ptr is either a link to a child or the root. When the loop stops, *cur is empty, and assigning to it attaches the new node.

The total cost grows with n squared

Look at the total comparisons for sorted input. The first insert costs 0, the second costs 1, and so on, up to n - 1 for the last one. The total is the sum of 0 through n - 1, which equals n(n-1)/2.

For 10 keys that gives 45, as printed. For 1,000 keys it gives 499,500, as printed. For 2,000 keys it gives 1,999,000.

Doubling the number of keys makes the work about four times bigger. This is the cost of building a chain. Every insert walks the whole chain built so far.

The same keys in a different order

Part 2 inserts the same ten keys in the order 5, 3, 8, 1, 4, 7, 9, 2, 6, 10. The height is 4, and the total is 19 comparisons, less than half of the 45 from the sorted run.

The first key, 5, becomes the root. Every later key goes left or right of 5 and then continues from there. The resulting tree looks like this:

            5
        /       \
       3         8
     /   \     /   \
    1     4   7     9
     \       /       \
      2     6         10

The root has two children, so the keys grow down both sides at once. That is why the height is small.

The input order decided this. If the same keys had arrived as 1, 2, 3, and so on, the root would have been 1, and every key would have gone to the right.

Measuring growth for larger sizes

Part 3 shows the pattern for four sizes.

For sorted input, the height equals n each time. The tree is a chain for every size.

For shuffled input, the height is 6 for 10 keys, 15 for 100 keys, 22 for 1,000 keys, and 24 for 2,000 keys. Each time the number of keys grows tenfold, the shuffled height grows by 7 to 9 levels. For sorted input, the same tenfold growth makes the tree ten times taller.

Random input usually gives a short tree, but the guarantee is only on average. An unlucky order can still make a tall tree. A shuffle is a helpful habit, but it is not a promise, and the next sections show how to get a real guarantee.

A worked search in each shape

Suppose you search for the key 1,000 in each tree.

In the sorted chain with 1,000 keys, the search starts at the root 1 and walks right, one node at a time. It visits 1,000 nodes before it finds 1,000. A key that is not in the tree and is bigger than every key also walks all 1,000 nodes before it stops.

In a tree with 1,000 keys and height 10, the search visits at most 10 nodes. The height of the balanced tree is found with bit_width(n) in the next lesson, and for 1,000 keys it is 10.

The difference is a factor of 100 in the number of steps for one search. The gap grows as the tree grows. For one million keys, a chain needs up to one million steps, and a tree of height 20 needs at most 20.

Sorted input in decreasing order makes the mirror image. Inserting 3, then 2, then 1 gives a chain that goes left from the root. It costs the same number of comparisons and has the same height.

Other orders that make long trees

Sorted order is the clearest bad case, but it is not the only one. The next program uses the same insert and height functions from the first program, and only main is new. It runs four orders of the keys 1 to 8.

int main() {
    vector<vector<int>> inputs = {
        {1, 2, 3, 4, 5, 6, 7, 8},
        {1, 2, 3, 4, 8, 5, 6, 7},
        {1, 8, 2, 7, 3, 6, 4, 5},
        {4, 2, 6, 1, 3, 5, 7, 8},
    };
    for (const auto& keys : inputs) {
        unique_ptr<Node> root;
        long long total = 0;
        for (int k : keys) total += insert(root, k);
        cout << "input";
        for (int k : keys) cout << " " << k;
        cout << "  height = " << height(root.get()) << "  total comparisons = " << total << "\n";
    }
}

Its output from g++ 15 is:

input 1 2 3 4 5 6 7 8  height = 8  total comparisons = 28
input 1 2 3 4 8 5 6 7  height = 8  total comparisons = 28
input 1 8 2 7 3 6 4 5  height = 8  total comparisons = 28
input 4 2 6 1 3 5 7 8  height = 4  total comparisons = 13

The first row is the sorted chain. The second row starts sorted, but the key 8 arrives early. Keys 5, 6 and 7 then go below 8 in order, forming the line 5, 6, 7. The path from the root to 7 is 1, 2, 3, 4, 8, 5, 6, 7, which is eight nodes, so the height is still 8.

The third row has no sorted run at all, and it is still a chain. Each new key lands directly below the key inserted just before it, so the path keeps growing. A reader might think this input looks random, but for this tree it is as bad as sorted input.

The fourth row uses the same keys as the first row in a different order. Its height is 4, and only the key 8 goes deeper than level 3, because it lands under 7.

Sorted input is not the only cause. A long tree appears whenever each key keeps extending the same path. The insert cost is the number of nodes on that path, so a long path costs a lot on every insert.

Three ways to avoid a chain

There are three common answers. Each has a cost.

The first answer is to change the order of the input. If you can shuffle the keys before inserting them, the tree is usually short. The shuffled rows in the output above show this. The cost is that you must control the order, and many real sources do not let you. A log file that is written in time order gives you sorted keys, and you cannot shuffle the log without extra work.

The second answer is to build the tree from a sorted array all at once. The middle key becomes the root, and each half is built the same way. This gives a tree of the smallest possible height. It is covered in the next lesson, "Sorted array to a height-balanced BST". It works only when you have all the keys at the start, and it does not handle later inserts.

The third answer is to fix the shape after each insert. A self-balancing tree checks its shape after every insert and changes a few links when a branch grows too long. The change is called a rotation, which moves one node up and one node down while keeping the BST rule. The AVL rotations lesson and the red-black tree lesson later in this module cover two ways to do this. The cost is extra code and a little extra work on each insert, and the benefit is a guaranteed height.

Common mistakes

Thinking the tree is broken because it looks like a line

A chain is a valid binary search tree. Every node is still greater than its left side and smaller than its right side. The shape is the problem, not the rule. Check the rule with a traversal that visits the left subtree, then the node, then the right subtree. The keys come out in sorted order, so the tree is valid even though it is slow.

Counting height in edges instead of nodes

Some textbooks count height as the number of edges, which are the links between nodes. A chain of 10 nodes has 9 edges. This lesson counts nodes, so the same chain has height 10. The program above prints 10. Before you compare two numbers, check which convention each source uses.

Passing a unique_ptr by value

A unique_ptr has exactly one owner. Copying it would give two owners and a double free, so the compiler refuses to copy it. This code fails:

unique_ptr<Node> root = make_unique<Node>(4);
auto copy = root;

g++ 15 prints this error (the file name and line numbers depend on your file):

copy.cpp:6:13: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]’
    6 | auto copy = root;
      |             ^~~~

The fix depends on what you want. To pass a tree to a function that only reads it, pass a const Node* or a const unique_ptr<Node>&. To hand ownership to another variable, write auto copy = std::move(root);. After the move, root is empty.

Recursing on a deep chain

The height function calls itself once for each level of the tree. A chain of 100,000 nodes makes 100,000 nested calls. This is fine for the sizes in this lesson, but the call stack has a fixed size. Very deep recursion can crash the program. The fix for large trees is an explicit loop with a stack or a queue, which the iterative traversal lessons in the binary trees module cover.

Practice

Exercise 1. Insert 20, 30, 40, and 50 into an empty binary search tree, in that order. What is the height, and how many comparisons does the whole sequence take?

Show the answer

The tree is a chain going right, so the height is 4. The inserts cost 0, 1, 2, and 3 comparisons, which is 6 in total.

Exercise 2. Find an order of the keys 1 to 7 that builds a tree of height 3. Count the comparisons for that order.

Show the answer

Insert 4, 2, 6, 1, 3, 5, 7 in that order. The root is 4, the next two keys make the second level, and the last four keys fill the third level. The comparisons are 0, 1, 1, 2, 2, 2, and 2, which total 10. Sorted order costs 21 for the same seven keys.

Exercise 3. Give a formula for the total number of comparisons when you insert the keys 1 to n in sorted order. Check it against the output above.

Show the answer

The total is 0 + 1 + ... + (n - 1), which equals n(n - 1) / 2. For n = 10 it is 45, which matches Part 1 of the output.

Exercise 4. Using the chain from the sorted insert of 1 to 1,000, how many nodes does a search for 1,000 visit? How many does a search visit in a tree of height 10?

Show the answer

The chain visits 1,000 nodes, because each node has only one child and the key is at the bottom. A tree of height 10 visits at most 10 nodes, because a search never goes below the height of the tree.

Exercise 5. Write a function bool isChain(const Node* root) that returns true when no node has two children. Test it on the chain 1, 2, 3 and on a tree that has a left child under the root.

Show the answer

The function walks down from the root. If the current node has both children, it returns false. Otherwise it moves to the one child that exists, or stops when there is none.

bool isChain(const Node* n) {
    while (n) {
        if (n->left && n->right) return false;
        n = n->left ? n->left.get() : n->right.get();
    }
    return true;
}

Run on the chain 1, 2, 3, it prints 1 (true). After adding a left child 0 under the root 1, it prints 0 (false). This is the output from g++ 15 for that test.

chain: 1
with left child: 0

Summary

• Inserting keys in sorted order makes each key the new deepest node, so the tree becomes a chain with height n.
• An insert that makes a chain costs about n(n-1)/2 comparisons for n keys, which grows faster than n.
• A search costs at most the height of the tree, so a chain makes every search cost up to n steps.
• Shuffling the input usually gives a short tree, but only on average, and many sources do not let you shuffle.
• A balanced build from a sorted array gives the smallest height, and self-balancing trees keep the height small after each insert.
• Height is counted in nodes in this course. Check which convention a source uses before you compare numbers.