Unit 2.5 · about 5 h
100 / 324Binary search trees, balance and augmented trees
BSTs turn sorted search dynamic, but only balance keeps it logarithmic. Augmented trees reuse the same skeleton to answer rank and range questions.
- explain
- implement
You can now
- Explain the BST ordering invariant and why child-only checks accept invalid trees.
- Implement
search,insert,deletein all three cases, and bounded validation, with edge tests for duplicates and sentinels. - Explain AVL balance, rotations and the Fibonacci height bound, read red-black guarantees at survey level, and implement an augmented range-sum structure with differential tests.
Covers
- Binary-search-tree ordering, duplicates and deletion
- Balanced-tree vocabulary and worst-case guarantees
- Ranks, order statistics and augmented trees
Study, in this order
4 steps
- Binary search treesDSA Handbook - search, trees and heaps
What BST actually constrains; Search; Insert; Delete: the case readers get wrong; Validate; Inorder as a sorted iterator; What it actually costs
- AVL trees and rotationsDSA Handbook - search, trees and heaps
What an AVL tree actually promises; Four cases, decided by two questions; The single rotations: LL and RR; The double rotations: LR and RL; Why height stays small: the Fibonacci proof
Depth · Derive the four cases on fresh 3-node inserts on paper; full AVL insert and delete code is not required, since the chapter ships no reference solution.
- Red-black trees: an overviewDSA Handbook - search, trees and heaps
What a red-black tree is; The height bound, in one inequality; Choosing the library type; AVL versus red-black, in one paragraph
Depth · Survey level only: keep the bound, the library mapping and the one-sentence trade-off. Do not implement fixups; the chapter explicitly declines to teach them.
- Segment treesDSA Handbook - search, trees and heaps
Locating this pattern; What is stored, and where; Build; Point update; Range query; Why query is \(O(\log n)\)
Depth · Stop before When the structure bends (lazy propagation and dynamic trees are later work). Implement point update with sum only; LC 307 is not assigned.
Focus on
- Bounded validation passes
(lo,hi)down and checkslo < val < histrictly. The tree[5,4,6,null,null,3,7]passes every child-only check, yet node 3 sits in the right subtree of 5 and fails the inherited bound. - Hibbard deletion copies the inorder successor's value, then deletes the successor, which has at most one child. Never rewire the successor object into the deleted slot; that loses the left subtree.
- AVL dispatch asks two questions: which side is heavy (sign of the balance factor) and outer versus inner (sign agreement). Same sign rotates once; opposite signs rotate twice. Insert needs \(O(1)\) rotations because the subtree height returns to its old value.
- Segment-tree query visits at most four vertices per level because only the two boundary vertices split; interior vertices exit on exact match. The min/max clipping plus the empty-range guard is what makes that proof work.
Reproduce closed-book
[5,3,8,1,4,7,9] and assert inorder [1,3,4,5,7,8,9]; assert validation rejects [5,4,6,null,null,3,7] and LeetCode's [5,1,4,null,null,3,6]; delete 5 and assert inorder [1,3,4,7,8,9] with validation true. Implement a segment tree with point update and range sum: on [1,3,5,7,9,11,13,15], update index 3 to 6 and assert sumRange(2,5) is 31. Differential-test the segment tree against brute force on random arrays up to length 50.Traps
- Using
intsentinels (INT_MIN,INT_MAX) as initial bounds. A key equal to the sentinel breaks the check; use infinities, boxed nullable bounds or a wider type. - Deleting by rewiring instead of value copy, or forgetting to delete the successor copy afterwards. Both corrupt the ordering or duplicate a key.
- Counting segment-tree vertices as \(2n-1\) and allocating \(2n\). When \(n\) is not a power of two the implicit layout overflows; allocate \(4n\).
Practice
LeetCode 98: Validate Binary Search Tree
Validate with (lo,hi) bounds; failing cases [5,1,4,null,null,3,6] from the problem and [5,4,6,null,null,3,7], which passes child-only checks
Attempt cold with tags hidden: state the ordering invariant before coding. After submitting, read the AlgoMaster write-up for Validate Binary Search Tree (https://algomaster.io/learn/dsa/validate-binary-search-tree). Transfer check: solve one unseen tree problem on NeetCode (for example LC 105 Construct Binary Tree from Preorder and Inorder Traversal, https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) with solutions closed.
LeetCode 230: Kth Smallest Element in a BST
Early-exit inorder counting to \(k\); follow-up asks for better than \(O(n)\) memory
After submitting, read the AlgoMaster write-up for Kth Smallest Element in a BST (https://algomaster.io/learn/dsa/kth-smallest-element-in-a-bst).
Self-test
-
Show a tree that passes child-only BST checks but is not a BST, and state the check that rejects it.
In[5,4,6,null,null,3,7], every parent is correctly ordered against its own children, but node 3 sits in the right subtree of 5. Bounded validation rejects it: node 3 inheritslo=5and fails5 < 3. -
Why does Hibbard deletion of a two-child node always terminate?
It copies the inorder successor's value and recurses into the right subtree for the successor. The successor is the leftmost node there, so it has no left child and the recursion lands in the zero-child or right-only case at once. -
Derive the AVL height bound from the Fibonacci recurrence.
A height-h AVL tree is smallest when its subtrees are minimal with heights \(h-1\) and \(h-2\), giving \(T(h) = T(h-1) + T(h-2) + 1\) with \(T(0)=0\) and \(T(1)=1\). That solves to \(F(h+2)-1\) nodes, so \(n \ge F(h+2)-1\) forces \(h \le 1.44 \log_2(n+2)\): about 44 percent worse than perfectly balanced. -
Why is a segment-tree range query \(O(\log n)\) rather than \(O(n)\)?
At each level only the leftmost and rightmost visited vertices can straddle the query boundary and split; interior vertices match exactly and stop. That caps each level at four vertices over \(O(\log n)\) levels, with the empty-range guard absorbing the half-empty splits.
Completion criterion
Stop when
Delete and validation behave on the handbook cases, the segment tree matches brute force on random arrays, and you can derive all four AVL cases plus the height bound on a fresh insert.
Mark passed, then open 2.6 Only mark this when you can do it without notes.Leads to
- 2.6 Heaps and priority queues Heaps serve priority workloads where ordering is partial, not total.
- 2.7 Tries and prefix lookup Tries serve prefix workloads where key order is irrelevant.
Comes after
- 2.3 Binary search: intervals, bounds and feasibility predicatesOrdered search moves from static arrays to dynamic trees.
- 2.4 Tree representation and traversalsBST operations inherit these traversals and add the ordering invariant.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.