Binary Search Trees

You have a sorted list of one million user ids. Checking whether one id is present takes about 20 steps with binary search. Then a new user signs up. Inserting into a sorted array means shifting up to a million elements one place to the right.

A binary search tree (BST) keeps the ordering that makes search fast. It also lets you insert and delete without shifting anything. This lesson answers two questions: which rule turns a binary tree into a BST, and what that rule buys you.