Binary Search Trees

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A binary tree with one promise at every node: left subtree < node < right subtree. Inorder (left, node, right) reads the values sorted.

   #1
2. ↯use it when

   Sorted order or nearest-key questions on a changing set: floor/ceiling, kth smallest, successor, bookings. Handed a BST? Think inorder or a one-path walk.

   #2
3. { }template

   One-path walk: while (cur != null) cur = x < cur.val ? cur.left : cur.right; — search, insert, LCA and successor all start here.

   #3
4. O( )cost

   Search/insert/delete/floor = O(h). Balanced: h ≈ log₂ n (20 levels for 10 lakh keys). Sorted inserts into a plain BST: h = n − 1. TreeMap guarantees O(log n).

   #4
5. !trap

   Checking only left.val < node.val < right.val misses grandchildren. Pass (low, high) bounds down — as null/long, never Integer.MIN_VALUE sentinels.

   #5
6. !trap

   Recursive insert/delete must re-link: root.left = deleteNode(root.left, key); Drop the assignment and the change is lost.

   #6
7. ✦pro tip

   Delete with two children: copy the in-order successor (leftmost of the right subtree), then delete it from the right subtree — it has no left child.

   #7
8. ✦pro tip

   Successor/ceiling: every node bigger than x is a candidate — remember it and go left. The last candidate wins. O(h), O(1) space.

   #8
9. ✦pro tip

   TreeMap/TreeSet are red-black BSTs: floorKey ≤, ceilingKey ≥, lowerKey <, higherKey >. All return null when nothing qualifies.

   #9

Shaky on a card? Open the chapter or flip its recall cards.