Binary Search Trees

A binary search tree (BST) keeps one rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger. That rule gives binary search on a tree. To find a value, compare with the node and go left or right, discarding half of what remains at each step.

When the tree is balanced, search, insert and delete are all O(log n). If values are inserted already sorted, the tree becomes a long chain and falls back to O(n), which is why real systems use self-balancing trees.