Chapter 15 — Binary Search Trees (BST)
Chapter 15 — Binary Search Trees (BST)
Hey everyone! Welcome back to Namaste DSA!
Take a binary tree and add one simple rule — and you get a structure that searches, inserts, and deletes in O(log n). That rule turns a plain tree into a Binary Search Tree, the foundation of ordered maps and databases.
What we will cover:
- The BST ordering rule
- Search / insert in O(log n)
- Why inorder traversal gives sorted order
- Deletion (the tricky one)
- When a BST degrades to O(n) — and balancing
- Validating a BST
- Interview Questions
1. The BST Rule
┌─────────────────────────────────────────────────────────────┐ │ FOR EVERY NODE: │ │ everything in the LEFT subtree < node │ │ everything in the RIGHT subtree > node │ ├─────────────────────────────────────────────────────────────┤ │ │ │ (8) │ │ / \ │ │ (3) (10) │ │ / \ \ │ │ (1) (6) (14) │ │ │ │ 8's left subtree (3,1,6) all < 8 ✔ │ │ 8's right subtree (10,14) all > 8 ✔ │ └─────────────────────────────────────────────────────────────┘
This rule means at every node you can throw away half the tree — exactly like binary search, but on a tree.
2. Search & Insert — O(log n)
function search(node, target) {
if (!node) return null;
if (target === node.val) return node;
return target < node.val
? search(node.left, target) // go left
: search(node.right, target); // go right
}
function insert(node, val) {
if (!node) return new TreeNode(val); // found the spot
if (val < node.val) node.left = insert(node.left, val);
else node.right = insert(node.right, val);
return node;
}
HAND TRACE: search for 6 in the tree above at 8: 6 < 8 → go left at 3: 6 > 3 → go right at 6: found! ✔ (only 3 comparisons for the whole tree)
3. Why Inorder Gives Sorted Order
Inorder is Left → Node → Right. Since left is always smaller and right always larger, you visit values in ascending order automatically.
Inorder of the tree above → 1, 3, 6, 8, 10, 14 (sorted!) ✔
This is a favourite interview fact: "inorder traversal of a BST is sorted."
4. Deletion — Three Cases
┌─────────────────────────────────────────────────────────────┐ │ DELETING A NODE — 3 cases: │ ├─────────────────────────────────────────────────────────────┤ │ 1) LEAF (no children) → just remove it │ │ 2) ONE child → replace node with its child │ │ 3) TWO children → replace with INORDER SUCCESSOR │ │ (smallest value in the right subtree), then │ │ delete that successor │ └─────────────────────────────────────────────────────────────┘
function deleteNode(node, val) {
if (!node) return null;
if (val < node.val) node.left = deleteNode(node.left, val);
else if (val > node.val) node.right = deleteNode(node.right, val);
else {
if (!node.left) return node.right; // case 1 & 2
if (!node.right) return node.left;
// case 3: find inorder successor (min of right subtree)
let succ = node.right;
while (succ.left) succ = succ.left;
node.val = succ.val; // copy value
node.right = deleteNode(node.right, succ.val); // remove successor
}
return node;
}
5. When a BST Degrades to O(n)
If you insert already-sorted values (1, 2, 3, 4...), each new node goes right, and the tree becomes a straight line — basically a linked list!
Insert 1,2,3,4 in order: A "balanced" tree:
(1) (3)
\ / \
(2) (2) (4)
\ vs /
(3) (1)
\
(4) ← height n → O(n) ← height log n → O(log n)
The fix is self-balancing trees (AVL, Red-Black) that rotate nodes to keep the height ~log n. You don't need to implement these for most interviews — just know why they exist: to guarantee O(log n).
6. Validating a BST
Common trap: checking only left < node < right locally is NOT enough — every node must respect a range inherited from its ancestors.
function isValidBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) && // tighten max
isValidBST(node.right, node.val, max); // tighten min
}
Interview Questions — Quick Fire!
Q: What is the BST property?
"For every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering lets you discard half the tree at each step, giving O(log n) search, insert, and delete when the tree is balanced."
Q: Why does inorder traversal of a BST give sorted output?
"Inorder visits left, then node, then right. Because left values are always smaller and right values larger than the node, the visit order is ascending. It's a quick way to check if a tree is a valid BST too."
Q: How do you delete a node with two children?
"Replace it with its inorder successor — the smallest value in its right subtree — then delete that successor from the right subtree. The successor is guaranteed to be larger than everything on the left and smaller than the rest of the right, so the BST property is preserved."
Q: When does a BST become O(n) and how is it fixed?
"When insertions come in sorted order, the tree degenerates into a linked list of height n. Self-balancing trees like AVL or Red-Black rotate nodes on insertion/deletion to keep the height around log n, restoring O(log n) operations."
Q: What's the common mistake when validating a BST?
"Only comparing each node to its immediate children. A node deep in the left subtree must still be less than a high-up ancestor. The correct approach passes down a valid (min, max) range that tightens as you descend."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| BST rule | left < node < right, everywhere. |
| Search/insert | O(log n) balanced — discard half. |
| Inorder | Yields sorted order. |
| Delete 2 children | Use inorder successor. |
| Degrades to O(n) | Sorted inserts → use self-balancing. |
| Validate | Pass down a (min, max) range. |
What's Next?
Chapter 16: Heaps & Priority Queues — a tree that always keeps the smallest (or largest) element at the top, perfect for "top K" problems.
Keep coding, keep grinding! See you in the next one!
Post a Comment