Insertion Order Decides a Tree's Shape

The shape of a plain binary search tree, one that never rearranges itself, is decided entirely by the order its keys arrive in: the same keys can give a tree of height about log n or a chain of height n - 1. This card covers why, why sorted input is the worst case, and what a tall tree does to the cost of every operation.

An insert never moves an existing node; it attaches the new key as a leaf at the end of a search. So the first key becomes the root for good, the next keys settle beneath it, and every later key has to descend past all of them. Inserting 4, 2, 6, 1, 3, 5 puts a middle key at the root, and the rest split between its two sides.

Inserting the same keys in sorted order, 1 to 6, gives a different shape. Each new key is larger than every key already in the tree, so its search goes right at every node and it lands as the right child of the previous key. The result is a chain: a tree in which every node has at most one child, which is a linked list with an unused link in each node.

A run built both trees and printed heights of 2 and 5. Finding 6 took two comparisons in the first and six in the second. The gap widens with size. The run inserted 511 keys three ways and measured the result:

511 keys, sorted order: height 510, 511 comparisons to find 511
511 keys, middle first: height 8, 9 comparisons to find 511
511 keys, 100 random orders: height from 15 to 24, mean 18.2

Middle first means the middle key of each range is inserted before the keys on either side of it, which fills every level. Random orders gave heights a little more than twice that best case, which still grow in proportion to log n. Sorted order gave n - 1, and so does reverse sorted order, which builds the chain down the left side.

Every operation follows one path, so each costs O(h), and on the chain h is n - 1. Search, insert and delete all fall to O(n), no better than scanning a list, and building the chain by n inserts costs O(n²) in total. A recursive insert or traversal also needs one call per level, so a chain of a few thousand keys can exhaust the call stack. Sorted input is common in practice: identifiers from a counter, timestamps, rows read from a sorted file.

A self-balancing binary search tree avoids this by rearranging a few links after each insert or delete, so that its height stays O(log n) whatever the order. Java's TreeMap is one, built on a design called a red-black tree.