Binary Search Trees
The BST invariant (left < node < right) gives O(log n) search, insert, and delete - and why an inorder traversal comes out sorted.
On this page
A binary search tree adds one rule to a binary tree that changes everything: for every node, all values in its left subtree are smaller and all in its right subtree are larger. That single invariant turns a tree into a searchable structure with O(log n) operations - the tree equivalent of binary search.
The invariant and O(log n) search
Because smaller values live left and larger live right, searching is a series of "go left or go right" decisions, halving the remaining tree at each step - just like binary search on a sorted array:
// search a BST — O(h), where h is the height (O(log n) if balanced)
TreeNode search(TreeNode node, int target) {
while (node != null) {
if (target == node.val) return node;
node = target < node.val ? node.left : node.right; // one side each step
}
return null;
}Insertion follows the same descent, placing the new value where the search for it would end. The cost of all these operations is O(h), the tree's height - which is the whole catch.
Balance is everything
"O(log n)" assumes the tree is balanced - roughly as wide as it is deep. But insert sorted values into a plain BST and it degenerates into a linked list: each node has only a right child, height becomes n, and every operation is O(n).
insert 1,2,3,4,5 into a plain BST → 1
\
2
\
3 ← height n, not log n!This is why production code uses self-balancing BSTs (red-black trees, AVL trees) that rotate nodes
on insertion to keep the height at O(log n). In Java, TreeMap and TreeSet are red-black trees -
reach for them when you need sorted keys, range queries, or floor/ceiling operations in guaranteed
O(log n).
TreeMap and TreeSet give you sorted power
When a problem needs values kept in sorted order with fast insertion, or asks for 'the largest value less than x' (floor) or 'smallest value at least x' (ceiling), or all values in a range, use TreeMap / TreeSet. They're balanced BSTs, so those queries are O(log n) - a HashMap can't do ordered or range queries at all.
A balanced BST is a filing cabinet with evenly split drawers: to find a file you open the middle drawer, see whether your file sorts before or after, and halve your search each time - a few steps even for thousands of files. A degenerate BST (from inserting already-sorted data) is a single tall stack of papers: 'sorted,' technically, but to find anything you leaf through from the top, one sheet at a time. Same rule, ruined by shape - which is why self-balancing trees rotate to keep the drawers evenly filled.
Given a binary tree, determine whether it's a valid BST. A common wrong answer only checks that each node is greater than its left child and less than its right child. Explain why that's insufficient, and what the correct check tracks.
Why can a binary search tree's operations degrade to O(n)?
Key takeaways
- A BST keeps smaller values left and larger right of every node, enabling O(log n) search/insert/delete by halving at each step.
- Operations cost O(height); balance is what makes height O(log n).
- Inserting sorted data into a plain BST degenerates it into a linked list with O(n) operations.
- Self-balancing BSTs (red-black, AVL) rotate to keep height logarithmic; Java's TreeMap/TreeSet are red-black trees.
- Use TreeMap/TreeSet for sorted keys, range queries, and floor/ceiling - things a HashMap can't do.