Binary Search Trees

A BST is a binary tree with one extra rule: every node's key is greater than everything in its left subtree and smaller than everything in its right. That rule alone gives you sorted-set semantics with O(log n) insert, search, and delete — when the tree is balanced.

The invariant does the work

Because keys are ordered, search is a comparison at each node followed by a jump left or right. In a balanced tree of one million keys, that's about 20 comparisons. In a skewed tree (inserting 1, 2, 3, 4, 5 in order), the same tree degrades to a linked list and search collapses to O(n). Production BSTs (Red-Black, AVL) rebalance on every write to prevent this. The trees you write in an interview usually don't.

Delete is the tricky one

Three cases: leaf (null the pointer), one child (splice child up), two children (replace with inorder successor — smallest key in right subtree — then delete successor).

Inorder = sorted

An inorder traversal of a BST is always sorted ascending. This is the most-tested property in interviews: 'given a BST, is it valid?' — do an inorder walk and check each key is strictly greater than the previous one.

Common bugs to avoid

• Trusting local checks for validity. A node whose left grandchild is larger than the root still passes the local test. Use inorder or pass (min, max) bounds down.
• Losing subtrees on delete. After splicing, return the new subroot up the call chain.
• Assuming balance. In-order inserts of 1..n produce a linked list. Interviewers love this test case.

Try it

1. Write is_valid_bst(root) using the (low, high) bounds pattern. Every node must satisfy low < node.key < high; recurse with tightened bounds.
2. Add kth_smallest(root, k) — do an inorder walk and stop after emitting k keys. It should be O(h + k), not a full traversal.