Recap: Binary Search Trees

Bounds, not children; shape from insertion order; the successor for deletion; balance for guarantees.

Binary search trees come down to the seven ideas below, each listed with the card that covers it. Most of them follow from one rule, the ordering of whole subtrees, and from the fact that every operation walks a single path from the root.

What the topic established, and which card it was on
The idea	Where
Every key in a node's left subtree is smaller and every key in its right subtree larger, so a search follows one path	Binary Search Trees: Ordered for One Descent
A search and an insert take the same path, and a new key always becomes a leaf; duplicates need a stated rule	Search and Insert in One Descent
Validity needs a lower and an upper bound carried down from the ancestors, not a comparison with the children	Checking Only Each Node's Children
Insertion order decides the height, from about log n up to `n - 1` when keys arrive sorted	Insertion Order Decides a Tree's Shape
A node with two children takes its in-order successor's key, and the successor is deleted from the right subtree	Delete a Node With Two Children
Every operation is O(h); Java's `TreeMap` is a red-black tree that keeps h at O(log n)	Binary Search Tree in Python, Java and TypeScript
A balanced tree is the one structure of the three that changes cheaply and answers ordered questions cheaply	Binary Search Tree vs Sorted Array and Hash Table

Deletion is the operation with the most to remember, and its three cases differ only in how many children the node has. The second table sets them side by side. Only the last case touches two nodes, and both lie on one path down from the root, so every case costs O(h) on a tree of height h.

The three cases of deleting a key from a binary search tree
The node has	What happens	Why the order holds
No children	It is removed and its parent's link becomes empty	Nothing else moves
One child	The child moves up into its place	The child's subtree was already on the correct side of the parent
Two children	Its key is replaced by the successor's, and the successor is deleted	The successor is the next key in sorted order, and it has no left child

Together they let you search, insert into and delete from a binary search tree by hand, check whether a tree is valid, predict its height from the order its keys arrived, and decide when a balanced tree beats a hash table or a sorted array.

← → move through sections and cards