The binary-search-tree property

A binary search tree (BST) stores keys in a binary tree so that, for *every* node $x$: every key in $x$'s left subtree is $\le x.key$, and every key in $x$'s right subtree is $\ge x.key$. This must hold recursively — it is not enough that $x$'s immediate children obey it; *every* descendant must. Each node carries key, left, right, and a parent pointer p.

The single most important consequence: an inorder tree walk — recurse left, visit the node, recurse right — prints the keys in sorted order, in $\Theta(n)$ time. That falls straight out of the property: everything left of $x$ is $\le x.key$, everything right is $\ge x.key$, applied at every level.

Every operation is O(h)

Search, minimum, maximum, successor, predecessor, insert, and delete all run in $O(h)$ time, where $h$ is the height of the tree, because each traces a single path of length at most $h$. TREE-SEARCH(x, k) goes left when $k < x.key$, right when $k > x.key$ — at each node it definitively eliminates one subtree, exactly like binary search on a sorted array. TREE-MINIMUM is just "follow left until you can't"; the minimum is the leftmost node.

Insertion, and why order matters

TREE-INSERT descends with a *search pointer* x and a *trailing pointer* y (x's parent). When x falls off the tree (becomes NIL), y is the new node's parent, and the node is attached as a leaf — insertion never restructures existing nodes. This means the insertion order shapes the tree, and that is the catch:

- Random insertion order → expected height $O(\lg n)$ → all operations $O(\lg n)$. (This is the same analysis as randomized quicksort: the root acts like the first pivot.) - Sorted insertion order ($1, 2, 3, \dots, n$) → every key is larger than all before it → a right-skewed linear chain of height $n-1$ → all operations $\Theta(n)$, no better than a linked list.

That worst case is the entire motivation for the *balanced* trees of the next lesson.

Deletion in one breath

TREE-DELETE has three shapes. If $z$ has no children, unhook it. If $z$ has one child, splice the child into $z$'s place. If $z$ has two children, replace $z$ with its successor $y = $ TREE-MINIMUM(z.right) — and the key fact (provable) is that this successor *has no left child*, so it slots cleanly into $z$'s position without disrupting the left subtree. The TRANSPLANT helper does the pointer surgery for all three cases uniformly.

Worked example — build a BST, walk it sorted

Insert 5, 3, 8, 1, 4, 7, 9, 2 in that order. 5 becomes the root; 3 goes left of 5; 8 goes right of 5; 1 goes left of 3; 4 goes right of 3; 7 and 9 arrange under 8; 2 goes right of 1. The tree is *not* sorted by shape — but an inorder walk reads it out as 1, 2, 3, 4, 5, 7, 8, 9. The walk never compares keys; the BST property alone guarantees sorted output. This is "BST sort": $n$ inserts + one inorder walk, $\Theta(n\lg n)$ on random input, $\Theta(n^2)$ on sorted input — the same best/worst split as the trees that build it.