Order built into the shape
A binary search tree, or BST, is a binary tree with an ordering invariant: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. This rule turns searching into a sequence of comparisons that discards half the remaining tree at each step, much like binary search on a sorted array.
The core operations
- Search: start at the root, go left if the target is smaller, right if larger, stop when found or you fall off the tree.
- Insert: search for the key, then attach a new leaf where the search ended.
- Delete: removing a node with two children means replacing it with its in order successor, the smallest key in its right subtree.
An in order traversal, visiting left subtree, node, then right subtree, yields the keys in sorted order, a handy property.
The balance catch
These operations follow a single root to leaf path, so their cost depends on the tree height. A balanced tree stays shallow and fast. But inserting already sorted keys produces a long thin tree that degrades into a list, making operations slow. That weakness motivates self balancing trees.
Key idea
A binary search tree keeps smaller keys left and larger keys right, so search, insert, and delete follow one path whose length is the height, fast when balanced but degraded into a list when keys arrive sorted.