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.

The Rule That Defines a BST

A binary search tree is a binary tree that follows one extra rule at every node:

• Every value in the node's left subtree is smaller than the node's value.