Lesson 17.1 · Binary Search Trees
The BST Rule, Search and Insert
Left is smaller, right is larger, at every node. Search and insert follow one path from the root, so they cost O(height).
14 min
Think of it like this
Guessing a number with "higher" or "lower" hints. Each node is a guess; the answer tells you which half to keep, and you never look at the other half again.
1.One path, not the whole tree
To search for x: if the node is null, it isn't there. If x equals the node's value, found. If smaller, go left; if larger, go right. Each step goes one level down, so the cost is the tree's height h.
Insert does the same walk and attaches a new leaf where the search fell off the tree. Nothing else moves.
root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], x = 7Step 1/47 < 8, so 7 can only be in the left subtree. The whole right side (10, 14, 13) is skipped.
2.Height decides everything
Insert 1, 2, 3, 4, 5 in that order and every node goes right: the "tree" is a linked list with height n, and search is O(n). Inserting in random order gives height about 2·ln n on average. Self-balancing trees (AVL, red-black) rotate nodes after each insert to keep the height O(log n) always. Java's TreeMap and TreeSet are red-black trees.
Quick check
What is the height after inserting 50, 30, 70, 20, 40, 60, 80?
Remember
- The rule holds for whole subtrees, not just children.
- Search and insert cost O(h).
- Balanced trees keep h = O(log n).
Common mistakes
- Assuming every BST is balanced (sorted inserts produce a list).
Words used in this lesson
- BST
- Binary search tree: left subtree < node < right subtree, at every node.
- Height (h)
- The number of levels below the root on the longest path.
- Self-balancing
- A tree that restructures itself to keep its height logarithmic.