Binary search trees
A binary search tree keeps keys ordered so that searching, inserting, and deleting can each follow a single path from the root, which is fast when the tree is short.
The BST property
In a binary search tree (BST), every node's key is greater than all keys in its left subtree and less than all keys in its right subtree. This ordering applies to entire subtrees, not just immediate children. Duplicates are either forbidden or consistently placed on one side.
Searching
To find a key, start at the root: if the key equals the node's, stop; if it is smaller, go left; if larger, go right; if you reach an empty spot, the key is absent. Each step descends one level, so search costs O(h). Finding the minimum means going left as far as possible; the maximum, right as far as possible.
Insertion
Insertion searches for the key and, on reaching an empty spot, attaches a new node there. New keys always become leaves. Like search, insertion costs O(h). The tree's shape therefore depends on insertion order.
Deletion
Deleting a leaf simply removes it. Deleting a node with one child links that child to the node's parent. Deleting a node with two children replaces its key with its in-order successor (the smallest key in its right subtree) or predecessor, then deletes that successor node, which has at most one child. Each case costs O(h).
The height problem
If keys arrive in random order, the expected height is about 2 to 3 times log2(n), so operations are fast. But inserting already sorted keys, 1, 2, 3, ..., creates a chain where every node has only a right child, height n - 1, and every operation degrades to O(n), no better than a linked list. Self-balancing trees, covered in the next unit, fix this.
Ordered operations
Because a BST keeps keys ordered, it supports operations hash tables cannot do efficiently: in-order traversal gives sorted output; successor and predecessor find the next or previous key; range queries list all keys between a and b; and floor and ceiling find the closest keys at or below and at or above a value. Augmenting nodes with subtree sizes also allows finding the kth smallest key.
Validating a BST
A common mistake is checking only that each node is larger than its left child and smaller than its right child. That misses deeper violations. The correct check passes down an allowed range: each node's key must lie between bounds inherited from its ancestors, narrowing the range as you go left or right. Equivalently, an in-order traversal must be strictly increasing.
Worked example
Insert 50, 30, 70, 20, 40, 60, 80 in that order: 50 is the root; 30 and 70 its children; 20 and 40 under 30; 60 and 80 under 70. Height 2. Searching for 60: 60 > 50 go right to 70; 60 < 70 go left: found in 3 comparisons. Deleting 50, which has two children: its successor is 60, the smallest key in the right subtree; copy 60 into the root and delete the old leaf 60.
Key takeaways
In a BST, left subtree keys are smaller and right subtree keys larger than each node. Search, insert, and delete follow one path and cost O(h). New keys become leaves. Deleting a two-child node uses its in-order successor or predecessor. Random insertion gives height O(log n), but sorted insertion degrades to a chain with O(n) operations. BSTs support sorted traversal, successor, range, floor, ceiling, and kth-smallest queries. Validate BSTs with inherited bounds, not just child comparisons.
Flashcard
Left keys smaller, right keys larger
Check your understanding
Keys 10, 20, 30, 40, 50 are inserted into an empty BST in that order. What happens to search time?