9 min read

When a BST degrades

Sorted insertion, linked-list shaped trees, and what balancing buys you.

A binary search tree only stays useful while its shape stays shallow. Insert a sorted sequence and every new node lands on the same side, producing a tree that is structurally a linked list: search, insert and delete all decay from O(log n) to O(n), and the recursive implementations start overflowing the stack.

Balancing schemes — AVL, red-black, treaps — all buy the same guarantee: height stays within a constant factor of log n, so the bounds you reasoned about are the bounds you actually get. What they cost is rotation work on every mutation, and a lot more code to get right.

In an interview you will almost never be asked to implement balancing. You will be asked what happens without it — which is exactly the paragraph above.

00:00

The invariant people remember is 'left is smaller, right is bigger'. That is true, and it is not the whole rule.

00:42

The real invariant is about subtrees, not children. Every node in the left subtree — not just the left child — must be smaller.

01:35

Which means a local check can never validate a tree. Let me show you the counterexample everybody writes first.

02:50

Here is the fix. Instead of comparing to the parent, we carry a range down: low and high.

04:10

The root gets negative infinity to positive infinity. The left child inherits the same low but a new high.