2.4Binary search trees
The idea
A binary search tree keeps smaller keys on the left and larger keys on the right, so search follows one path.
Think of it like this: A game of "higher or lower": every guess throws away half of the remaining keys, if the tree is balanced.
Why it exists
BST operations are O(height): the shape of the tree decides everything.
How it works
- Search / insert: go left if smaller, right if larger.
- Delete a leaf: remove it.
- Delete a one-child node: link its parent to its child.
- Delete a two-child node: copy the inorder successor into it, then delete the successor.
Worked example: Insert 10, 20, 30, 40
Sorted input makes a right-leaning path of height 4: search is O(n). The same keys inserted in a balanced order give height 3.
Now play with it
- →Press "Sorted keys" to see the path form.
- →Press "Balanced keys" for the bushy tree.
(empty tree)
- empty tree
- insert 50
- insert 30
- insert 70
- insert 20
- insert 40
- insert 60
- insert 80
Inorder of a BST is always sorted. A plain BST built from sorted keys degenerates into a list (height n); the AVL tree keeps the height below 1.44 log₂ n. Numbers in grey are balance factors (left height − right height); red means a rotation is needed.
Check yourself
After inserting the keys 50, 30, 70, 20, 40 into an empty BST, the root of the left subtree is
Exam notes (the dense version)
Left subtree keys < node < right subtree keys. Search, insert and delete take O(h): O(log n) for a balanced tree but O(n) in the worst case (sorted insertions). Deleting a node with two children: replace it with its inorder successor (or predecessor), then delete that node. The number of BSTs with n keys is the Catalan number.
Previous year questions: Trees & Binary Search Trees (15)
PYQs are grouped by topic, so this is the full set for Trees & Binary Search Trees; try the ones that match this subtopic. Open all 15 on the topic page.