Binary search trees

The BST property, inorder = sorted, O(h) operations, and why sorted insertion degenerates to O(n).

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 $\leq x . k ey$ , and every key in $x$ 's right subtree is $\geq x . k ey$ . 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 $Θ (n)$ time. That falls straight out of the property: everything left of $x$ is $\leq x . k ey$ , everything right is $\geq x . k ey$ , 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 . k ey$ , right when $k > x . k ey$ — 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 (l g n)$ → all operations $O (l g 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 $Θ (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, $Θ (n l g n)$ on random input, $Θ (n^{2})$ on sorted input — the same best/worst split as the trees that build it.

Every key in a left subtree is ≤ its ancestor and every key on the right is ≥ it, at every level. That alone makes the inorder walk (left, node, right) read out 1, 2, 3, 4, 5, 7, 8, 9.

The BST worst case: each new key is larger than every key before it, so it is attached as the rightmost leaf. The tree becomes a linked list and every O(h) operation degrades to Θ(n).