Lesson 087
Binary Search Trees
Search · Insert · Delete · Balance
1:00How the left-less-than, right-greater-than ordering rule makes search, insert, and delete run in O(log n) — and what goes wrong when the tree degenerates.
By the end, you can
- State the BST ordering invariant and explain why it must hold at every node, not just immediate children.
- Trace the search path to any key in a BST diagram, identifying comparisons made and the outcome (hit or miss).
- Produce the in-order, pre-order, and post-order traversal sequences for a given BST.
- Identify the correct insertion slot for a new key by following the search path.
- Apply all three deletion cases (leaf, one child, two children) and find the in-order successor.
- Explain why inserting sorted keys into a plain BST yields O(n) worst-case performance.
- Describe why checking only parent-child comparisons fails to validate a BST, and state the correct approach.
- Name AVL and Red-Black trees as self-balancing BST variants that guarantee O(log n).
Up next in Trees, Hashing & Graphs
