Binary Search Trees and the BST Property

What This Concept Is

A binary search tree stores keys under an ordering relation. In this module's ordered-map contract, keys are unique integers: every key in the left subtree is strictly less than the node key, and every key in the right subtree is strictly greater. Setting an existing key replaces its value without adding a node.

This is a subtree-wide invariant, not merely a comparison with immediate children. Search follows one branch and takes O(h+1), where h is tree height. A plain BST can have height n-1 after sorted insertion; balancing requires another invariant. Keys, comparisons and mutable payloads need explicit contracts before generic use.

Why It Matters Here

Every balanced map retains this ordering while changing shape. The lab adds subtree sizes for rank/select, which makes rotations responsible for metadata as well as pointers. Ordered traversal, lookup correctness and complexity need different checks: a sorted output does not prove that the tree is balanced.

Concrete Examples

A local check that fails. Root 10 has left child 5, whose right child is 12. Each parent/child pair looks ordered, but 12 lies in 10's left subtree and violates its upper bound. Validate recursively with inherited lower/upper bounds, or equivalent global ordering plus acyclicity and identity checks.

Rotation. For node x with right child y, let subtrees be A=x.left, B=y.left, C=y.right. Their key order is A < x < B < y < C. A left rotation makes y the parent, x its left child and B the right child of x. The order is unchanged. Recompute x's metadata before y's because y now reads x.

Deletion. With two children, replace the key/value with the inorder successor from the right subtree, then remove that successor from its old location. Moving only its key would associate the wrong payload with a key. Ancestor sizes and balance metadata need repair on the affected path.

For keys [10,5,12,7], sorted items are [5,7,10,12], rank(10)=2, and zero-based select(1)=7. Rank counts keys strictly below the argument, even if the argument is absent. Replacing key 7's value leaves all ranks unchanged.

Common Confusion / Misconceptions

Duplicate policies cannot be left implicit. A multiset might use counts per node; directing equals to one side can interact badly with rotations. Pointer cycles, aliased children and stale subtree sizes may coexist with correct lookup answers. Input insertion order alone determines shape only for a specified plain insertion algorithm without later balancing/deletion, not for every BST.

How To Use It

Write the key and replacement contract. Validate global bounds, unique node identity, height and size metadata. Compare lookup/rank/select after every operation against a dictionary and sorted keys. Exercise replacing values, removing the root and deleting nodes with zero, one and two children. Preserve the operation sequence that first breaks the invariant.

Check Yourself

Why can immediate-child comparisons miss an ordering violation? Which metadata changes in a rotation? Why does replacing a value not change rank?

Mini Drill or Application

Insert 3,1,2, replace key 1's value, then delete 3. Report ordered keys and rank(2). Feedback: [1,2] and 1, regardless of valid balanced shape. Explain where the replacement value must remain after rotations.

Read This Only If Stuck

Skiena: binary search trees and balanced search trees. Use the local contents index; the assignment is by topic, not a guessed deep chapter link.