COMP9123 — Week 5
Foundations & proof moves
Week 5 foundations turn the BST and AVL stories into reusable proof templates: why inorder is sorted, why local checks are not enough for BST validation, how height relates to node count, and how augmentation turns a search tree into a statistics data structure.
Inorder Proof: Why BSTs Yield Sorted Output
Tutorial 5 makes you prove the most famous BST fact: inorder traversal always returns keys in ascending order. The point is not just to memorise the claim. The point is to see how the recursive BST invariant becomes a recursive proof.
Assume the left subtree and right subtree already produce sorted inorder sequences. The BST property then guarantees every key in the left sequence is smaller than the root, and every key in the right sequence is larger than the root.
The proof skeleton in one line
inorder(T) = inorder(T_left), root, inorder(T_right)
If both subtree outputs are sorted and all left keys are less than the root while all right keys are greater, then the concatenated whole is sorted as well.
What the proof is really using: not just the traversal order, but the BST property plus induction on subtree height or tree size.
Global BST Checking: Local Parent-Child Tests Are Not Enough
One of the best tutorial questions gives a flawed BST-checking algorithm that compares each node only to its immediate children. That algorithm fails because BST correctness is global, not merely local.
A node can sit in the right subtree of the root, pass every local parent-child comparison there, and still be smaller than the root, which violates the BST property.
Correct validation idea
Carry a valid key interval down the recursion. Every node must fall within the range implied by all its ancestors, not just by its parent.
Related structural queries
The tutorial's largest() and second-largest() problems rely on the same global reasoning: the rightmost path determines where the maximum lives, but the second largest needs case analysis about the maximum node's left subtree and parent.
Height & Node-Count Facts: Why Balanced Trees Matter
Tutorial 5 uses induction to make the height story precise. A binary tree of height \(h\) can hold at most \(2^h - 1\) internal nodes in the most compact case, so any BST with \(n\) internal nodes must have height at least \(\log_2 n\).
| Fact | Interpretation | Why Week 5 cares |
|---|---|---|
| Maximum nodes at height \(h\) | \(2^h - 1\) for the fullest binary shape | This yields the lower bound \(h \ge \log_2 n\). |
| External nodes in a BST with \(n\) internal nodes | \(n + 1\) | Useful for reasoning about search endpoints and tree structure. |
| AVL minimum-size recurrence | Minimal AVL trees grow fast enough with height to force logarithmic height | This is the proof intuition behind AVL performance. |
Performance translation: plain BSTs can have height anywhere between \(\Theta(\log n)\) and \(\Theta(n)\), while AVL trees are designed to stay in the logarithmic regime.
Augmentation & Order Statistics: Make the Tree Answer Richer Queries
The tutorial goes beyond search and update operations by asking for median(), rank-based sums, and efficient range deletion. The common pattern is augmentation: store small extra summaries at each node so that a root-to-leaf walk can answer much more than membership.
| Query | Extra information needed | How it helps |
|---|---|---|
| Median / select \(k\)-th smallest | Subtree size at each node | You can decide whether the target rank lies left, at the root, or right in \(O(1)\) work per level. |
| Rank sum | Subtree sizes plus subtree key sums | Prefix information accumulates during one guided descent. |
| Weighted median | Weight sums over subtrees | The root-to-leaf search is driven by cumulative weight instead of element count. |
| Remove all in \([k_1, k_2]\) | BST order plus careful bulk pruning | The target complexity \(O(h+s)\) comes from combining navigation with subtree removal. |
Big design habit: when a query keeps asking about rank, count, sum, or weight, ask whether a small per-node summary field would let each recursive decision skip most of the tree.
Quick checks
The Week 5 foundations checks now sit directly under the inorder proof, global-validation, and augmentation sections above so you can test each reasoning move where it first appears.
Tutorial PDF review
Treat Tutorial 5 as the point where the course stops being satisfied with “I know the data structure” and starts asking “Can you prove it, debug it, and augment it?”
Tutorial 5 checklist. You should be comfortable proving inorder sortedness by induction, explaining why local child comparisons do not fully validate a BST, finding largest and second-largest in \(O(h)\), deriving the node-count and external-node facts, and explaining why subtree-size augmentation makes median or select queries possible in one root-to-leaf walk.