← BST · guided lesson
Binary Search Trees
the story
Binary search tree
Every tool here exists because something was too slow or broke without it. Here is what.
Around 1960 several researchers arrived at the same idea on their own: keep keys in a tree where smaller keys go left and larger keys go right. Windley (The Computer Journal, 1960) and Booth with Colin (Information and Control, 1960) built such trees one key at a time. Hibbard's 1962 paper in the Journal of the ACM studied these trees mathematically, for searching and sorting, and gave a way to delete keys from them.
the problem it solved
A dictionary you can search like a sorted list, yet grow one key at a time without shifting everything after it.
why it matters: without it
You'd choose between a sorted array (fast search, O(n) inserts) and a hash table (fast inserts, no order) — nothing would give you both, plus "next bigger key", in O(log n).
sources: P. F. Windley — Trees, Forests and Rearranging (The Computer Journal, 1960) ↗ · A. D. Booth & A. J. T. Colin — On the efficiency of a new method of dictionary construction (Information and Control, 1960) ↗ · T. N. Hibbard — Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting (JACM, 1962) ↗ · Binary search tree — history (independent discovery by Windley, Booth, Colin and Hibbard) ↗
also in this chapter: BST delete with the in-order successor (Hibbard deletion) · Self-balancing BST (AVL tree)
the idea
The idea in 30 seconds
A BST is a binary tree with one promise: everything left of a node is smaller, everything right is larger — at every node, not just its children.
So searching is binary search: compare, then throw away a whole side. Cost = the height h, which is O(log n) when the tree is balanced.
Read it in order (left → node → right) and you get the values sorted. Java's TreeMap/TreeSet are self-balancing BSTs that guarantee O(log n).
picture this
Your phone's contact list, searched by halves: open the middle, "Priya" is after "Neha", so drop the first half. A BST stores those halving checkpoints as nodes — so adding Rahul only hangs one new node at the bottom, instead of shifting every name after him.
watch it
Search — one path, half thrown away each step
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Search — one path, half thrown away each step
Grey nodes are ruled out the moment we turn the other way. The number of comparisons is at most height + 1.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Insert — search, fall off, attach
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Insert — search, fall off, attach
The new value always becomes a leaf. Nothing else moves.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
BST property: for every node, all values in its left subtree < node < all values in its right subtree. Checking only the direct children is not enough.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Inorder traversal of a BST is sorted. Many BST problems are just "inorder, with a twist" (validate, kth smallest, iterator, minimum difference).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Search / insert / delete all walk one root-to-leaf path: O(h). A balanced tree has h ≈ log₂ n; a degenerate one (sorted inserts) has h = n − 1.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Insert = search until you fall off the tree, then hang the new value there as a leaf.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Delete has 3 cases: leaf → unlink; one child → the child takes its place; two children → copy the in-order successor (leftmost node of the right subtree), then delete that successor (which has no left child).
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Successor / floor / ceiling = a walk that remembers the best candidate on the way down: every node bigger than x is a candidate for "next larger", and each new one is closer.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Self-balancing BSTs (AVL, red-black) rotate after inserts/deletes to keep h = O(log n) always. Java's TreeMap and TreeSet are red-black trees — use them instead of writing your own.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Ordered queries are a BST's superpower over a HashMap: floor, ceiling, lower, higher, first, last, ranges — each O(log n) in a TreeMap.
spot the pattern
When you see this, think this
The input is a BST and you need sorted order
Inorder traversal (iterative with a stack if you need to stop early)
"Validate" / "is this a BST"
Pass (low, high) down, or check inorder is strictly increasing
Find / insert / delete / closest value in a BST
Walk one path using comparisons: O(h), O(1) space iteratively
"Next larger" / "successor" / "previous smaller" of a node
Walk from the root remembering the best candidate (or
TreeMap.higherKey)
+5 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Checking only
left.val < node.val < right.val— a grandchild can still break the rule (5 → right 6 → left 3). - Using
Integer.MIN_VALUE/MAX_VALUEas range sentinels when node values can be exactly those — useLongbounds ornullfor "no limit".
quick check
One question. No pressure.
Is [5, 4, 6, null, null, 3, 7] a valid BST?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Delete Node in a BST
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What exactly does the BST property promise?
Question 1: What exactly does the BST property promise?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.