§3Exercises
Ten exercises in four layers: three proofs, two designs, three implementations with milestones, and two read-the-code. Proofs and designs are the same in both languages; the implementation exercises come as templates in PythonJava with tests that fail on purpose, and your job is to make every test pass. Try each exercise before you open its solution.
| # | Layer | Topic | Video |
|---|
| 1 | Proof | Insertion keeps the order | 2 |
| 2 | Proof | Height versus size | 1, 4 |
| 3 | Proof | Counting trees; which walks determine a tree | 1, 2, 4 |
| 4 | Design | Which structure for which workload? | 2, 4 |
| 5 | Design | Order statistics: the k-th smallest key | 2, 3 |
| 6 | Implement | Inorder iterator, height and is_bst without recursion | 1, 2 |
| 7 | Implement | A BST that counts its comparisons | 2, 4 |
| 8 | Implement | Delete: leaf, one child, two children | 3 |
| 9 | Read the code | An AI-written delete that "works" | 3 |
| 10 | Read the code | An AI claims a search is O(h) | 2 |
PROOFS
Exercise 1 · Insertion keeps the order. A binary search tree (BST) with distinct keys is a binary tree in which, for every node, all keys in its left subtree are smaller than its key and all keys in its right subtree are larger. Let T be a BST and k a key that is not in T. Insertion walks down from the root: at node x go left if k < x.key and right otherwise; when the child you want is empty, attach a new leaf with key k there. (a) Give a loop invariant about k and the subtree rooted at the current node x. (Hint: every node's subtree has an allowed open interval of keys, (lo, hi); the root's is (−∞, +∞).) Prove initialization and maintenance. (b) Use (a) to prove that the tree is still a BST after the insertion. Where do you use that k is not already in T? (c) A programmer tests "is this a BST?" by comparing every node only with its two children. Give a tree with four nodes that passes this test but is not a BST, and say which check (a) suggests instead.
Solution
(a) For a node x of T let lo(x) be the largest key among the ancestors a of x with x in a's right subtree (−∞ if there is none) and hi(x) the smallest key among the ancestors with x in their left subtree (+∞ if none). Invariant, true every time the loop looks at a node x:
Because lo(x) is the largest and hi(x) the smallest of the relevant ancestor keys, the invariant says exactly that k is on the correct side of every ancestor of x. Initialization: x = root has no ancestors, lo = −∞, hi = +∞. ✓ Maintenance: assume lo(x) < k < hi(x). Since k is not in T, k ≠ x.key. If k < x.key we move to the left child y: lo(y) = lo(x) and hi(y) = x.key (x is the nearest ancestor with y in its left subtree, and it is smaller than the old hi(x) by the BST property), so lo(y) < k < x.key = hi(y). If k > x.key we move right: lo(y) = x.key and hi(y) = hi(x), so x.key < k < hi(y). ✓ The walk ends because the tree is finite; it stops at an empty child, where the new leaf N is attached, and lo(N) < k < hi(N) still holds.
(b) After the insertion only the ancestors of N have a subtree that changed (it gained k). For an ancestor a, N is in a's left subtree iff the walk went left at a, which happened because k < a.key; it is in the right subtree iff k > a.key (here we use that k is not in T: if k were equal to a key on the path, the walk would send it right while the tree needs a strict inequality, so a duplicate would break the property). Every other node keeps the same subtrees. N itself has two empty subtrees, so its condition holds vacuously. Hence the tree is a BST. ∎
(c) Root 50, left child 30, right child 70, and 60 as the right child of 30. Every node is larger than its left child and smaller than its right child, so the children-only test passes, but 60 lies in the left subtree of 50 and is larger than 50. The correct check carries the interval of (a) downwards: the root must lie in (−∞, +∞); a node with key v in (lo, hi) passes (lo, v) to its left child and (v, hi) to its right child. Equivalently: the inorder walk must be strictly increasing (Exercise 6).
Exercise 2 · Height versus size. Count the height in edges (a single node has height 0, the empty tree −1). (a) Prove by induction on d that a binary tree has at most 2ᵈ nodes at depth d. (b) Conclude that a binary tree of height h has at most 2^(h+1) − 1 nodes, so a tree with n nodes has height h ≥ log₂(n + 1) − 1. Compute the smallest possible height for n = 1,000 and n = 10,000 (compare with the "perfect height" column of video 4). (c) Prove that h ≤ n − 1 for every binary tree with n nodes, and describe the trees with equality. (d) Conclude: in every BST with n keys some key needs at least ⌈log₂(n + 1)⌉ comparisons to be found (count one comparison per visited node), and no key needs more than n.
Solution
(a) Depth 0 holds 1 = 2⁰ node (the root). If depth d holds at most 2ᵈ nodes, every one has at most two children, so depth d + 1 holds at most 2·2ᵈ = 2^(d+1). ∎
(b) n ≤ Σ_{d=0}^{h} 2ᵈ = 2^(h+1) − 1 (the geometric sum of chapter 1, Exercise 2(a)). So 2^(h+1) ≥ n + 1, i.e. h + 1 ≥ log₂(n + 1), and since h is an integer h ≥ ⌈log₂(n + 1)⌉ − 1. For n = 1,000: log₂ 1001 ≈ 9.97, so h ≥ 10 − 1 = 9. For n = 10,000: log₂ 10001 ≈ 13.29, so h ≥ 14 − 1 = 13. These are the "perfect height" numbers 9 and 13 of video 4.
(c) A node at depth h has one ancestor at every smaller depth, so every depth 0, 1, …, h contains at least one node and n ≥ h + 1. Equality holds when every level has exactly one node, i.e. every node has at most one child: a chain (which may zigzag between left and right children).
(d) Finding a key at depth d visits d + 1 nodes, i.e. makes d + 1 comparisons. The key at the deepest level, depth h, needs h + 1 ≥ ⌈log₂(n + 1)⌉ comparisons by (b), so no BST, however clever, has every key within fewer. By (c) h + 1 ≤ n, so no key needs more than n. Video 4 shows both ends: the chain (n) and a good tree (about log₂ n).
Exercise 3 · Counting trees. Let Cₙ be the number of different binary tree shapes with n nodes. (a) Show that C₀ = 1 and Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ·Cₙ₋₁₋ᵢ. Compute C₁, …, C₅. (b) Explain why the number of different BSTs that hold the keys {1, …, n} is also Cₙ. (c) For n = 3 list all the BSTs on {1, 2, 3} and, for each, the insertion orders (among the 6 permutations) that build it. If the six orders are equally likely, which tree is the most likely and with what probability? What does this say about "random insertion order" and balance? (d) Show that the inorder walk does not determine a BST (give two BSTs on {1, 2} with the same inorder walk), but the preorder walk does: prove by strong induction on n that two BSTs with the same preorder sequence are equal.
Solution
(a) The empty tree is the only shape with 0 nodes: C₀ = 1. A shape with n ≥ 1 nodes is a root, a left subtree with i nodes and a right subtree with n − 1 − i nodes (0 ≤ i ≤ n − 1), and the two subtrees can be chosen independently: Cₙ = Σᵢ Cᵢ·Cₙ₋₁₋ᵢ. Then C₁ = 1, C₂ = C₀C₁ + C₁C₀ = 2, C₃ = 2 + 1 + 2 = 5, C₄ = 5 + 2 + 2 + 5 = 14, C₅ = 14 + 5 + 4 + 5 + 14 = 42. (These are the Catalan numbers.)
(b) Let Bₙ be the number of BSTs on {1, …, n}. B₀ = 1. Choose the root key r; the keys 1, …, r − 1 must all go into the left subtree, which can be any BST on those keys, and r + 1, …, n into the right subtree. So Bₙ = Σᵣ B_{r−1}·B_{n−r}, the same recurrence with the same start as Cₙ; hence Bₙ = Cₙ.
(c) The five BSTs and the orders that build them:
| tree | insertion orders |
|---|
| 1 → 2 → 3 (right chain) | 1 2 3 |
| 1, right child 3, whose left child is 2 | 1 3 2 |
| root 2 with children 1 and 3 (balanced) | 2 1 3 and 2 3 1 |
| 3, left child 1, whose right child is 2 | 3 1 2 |
| 3 → 2 → 1 (left chain) | 3 2 1 |
The balanced tree is built by two of the six orders, so it has probability 2/6 = 1/3; every other tree has probability 1/6. Random insertion order does not give a uniformly random shape: balanced shapes are favoured (twice as likely as any particular chain for n = 3, and more strongly for larger n), which is why random insertion keeps trees short on average (video 4).
(d) Two BSTs on {1, 2}: root 1 with right child 2, and root 2 with left child 1. Both have the inorder walk 1, 2. In any BST the inorder walk is the sorted list of the keys, so it carries no information about the shape. Claim: two BSTs with the same preorder sequence p₁, …, pₙ (distinct keys) are equal. Strong induction on n. n = 0: both empty. n ≥ 1: preorder visits the root first, so both roots are p₁. Preorder then visits the whole left subtree and afterwards the whole right subtree; in a BST the left subtree holds exactly the keys smaller than p₁ and the right subtree exactly the larger ones, so the sequence is p₁, (all keys < p₁), (all keys > p₁). The cut point (the first key larger than p₁) depends only on the sequence, so both trees have left subtrees with the same preorder sequence, and right subtrees with the same one, each with fewer than n nodes. By the induction hypothesis the left subtrees are equal and the right subtrees are equal. ∎ (This is why inserting the keys of a BST in its preorder order rebuilds the same tree.)
DESIGNS
Exercise 4 · Which structure? For each workload choose among a sorted array with binary search, a hash table (chapter 7), a plain BST (this chapter) and a balanced BST (chapter 6). Justify with the cost of each operation, and say what the worst case of a plain BST would be. (A) One million keys are loaded once, then ten million lookups; nothing changes afterwards. (B) Arbitrary keys are inserted, deleted and looked up all day; the only query is "is this exact key present?". (C) Arbitrary keys are inserted and deleted all day; queries also ask for "the smallest key ≥ x" and "all keys between a and b". (D) One million ids arrive in increasing order; the operations are "append the new id" and "look an id up".
Solution
| workload | choice | why | plain BST |
|---|
| A. load once, 10⁷ lookups | sorted array + binary search (a hash table is equally fine if no order is needed) | lookup ⌈log₂(n+1)⌉ ≈ 20 comparisons, no pointers, compact; no updates, so there is nothing a tree would add | works if built balanced; no advantage and more memory |
| B. insert / delete / exact lookup | hash table (balanced BST also fine) | expected O(1) per operation (chapter 7); a balanced tree gives O(log n) | O(log n) only for random order, O(n) per operation for sorted keys |
| C. updates plus "smallest key ≥ x" and ranges | balanced BST (TreeMap in Java) | floor / ceiling and range queries in O(log n + k) and updates in O(log n); a hash table cannot answer ordered queries without scanning all n keys, and a sorted array pays O(n) per insertion | O(h): fine for random order, a chain if the keys arrive sorted |
| D. ids arrive in increasing order; append and look up | sorted dynamic array | append is O(1) amortized (chapter 1), lookup is binary search O(log n) | the worst case of all: every insertion goes to the far right, h = n − 1, and inserting n = 10⁶ ids makes n(n − 1)/2 ≈ 5·10¹¹ comparisons (the same number as Program A in video 1 of chapter 1) |
A hash table would also serve D, but only if the ids need no order; the sorted array gives order for free.
Exercise 5 · Order statistics. An order-statistic tree is a BST in which every node also stores size, the number of keys in its subtree (itself included). (a) State the invariant that size must satisfy. (b) Design select(k) (the k-th smallest key, k = 1 is the minimum) and rank(key) (the number of keys smaller than key). Give the algorithms, their cost, and check them on the tree of video 2 (keys 50, 30, 70, 20, 40, 60, 80): what are select(4) and rank(60)? (c) What must insert and delete do to keep the invariant, and what does it cost? (d) How do the costs behave if the keys are inserted in sorted order into a plain BST, and what would fix that?
Solution
(a) size(empty) = 0 and size(x) = 1 + size(x.left) + size(x.right) for every node x.
(b) select(k), 1 ≤ k ≤ size(root):
x = rootloop: r = size(x.left) + 1 # x is the r-th smallest key of its subtree if k == r: return x.key if k < r: x = x.left else: k = k - r; x = x.right
The keys of the left subtree are the size(x.left) smallest keys of x's subtree, x is the next one, and the rest are in the right subtree; so the k-th key is in the left subtree if k < r, is x if k = r, and is the (k − r)-th key of the right subtree otherwise. rank(key), the number of keys smaller than key:
x = root; count = 0while x is not empty: if key <= x.key: x = x.left # x and its right subtree are not smaller else: count = count + size(x.left) + 1; x = x.right # x and its left subtree are smallerreturn count
Both follow one path from the root: O(h). On the tree of video 2 the left subtree of 50 has 3 keys (20, 30, 40), so r = 4 and select(4) = 50. rank(60): at 50, 60 > 50, count = 3 + 1 = 4, go right; at 70, 60 ≤ 70, go left; at 60, 60 ≤ 60, go left: empty; result 4 (the keys 20, 30, 40, 50).
(c) insert: first search; if the key is already there do nothing; otherwise, on the walk down to the new leaf add 1 to the size of every node on the path (each gains one key); the new leaf has size 1. delete: when a node is removed, subtract 1 from the size of every node on the walk from the root to the node that is physically removed (in the two-children case that walk continues down to the in-order successor). Both are one extra constant-time step per node of a path the operation walks anyway: still O(h). (Chapter 6's rotations will recompute the size of the two nodes they move from their children.)
(d) Sorted insertion into a plain BST gives a chain, h = n − 1, so select, rank, insert and delete are all O(n). Keeping the tree balanced (AVL, red-black) keeps h = O(log n), and all four become O(log n); this is how real order-statistic trees are built.
IMPLEMENTATIONS (WITH MILESTONES)
Each file lists its milestones at the top. Do them in order and run the tests after each one.
Exercise 6 · Walks without recursion — ex_walks.pyExWalks.java. Write an inorder iterator with an explicit stack, then height level by level, then is_bst on top of your iterator. The tests check the output, that the stack never holds more than height + 1 nodes, that a chain of 50,000 (Java: 200,000) nodes does not run out of stack, and that the tree from Exercise 1(c) is rejected.
Solution
Reference code: solutions/py/ex_walks.py, solutions/java/ExWalks.java. The iterator keeps a stack holding the nodes whose left subtrees are being explored: the constructor pushes the left spine; next() pops the top (the smallest key not yet returned), then pushes the left spine of its right child, which is exactly the next part of the walk. Every node is pushed and popped once, so the whole walk takes O(n) and each next() O(1) amortized. Why the stack never holds more than h + 1 nodes: at every moment the stack contains only ancestors of the next node to be returned (together with that node), and those lie on one root-to-node path, which has at most h + 1 nodes. height goes level by level (a list of the nodes at the current depth), which needs no recursion and counts edges (start at −1). is_bst is the observation of video 2: the inorder walk of a BST is strictly increasing, and a tree whose inorder walk is strictly increasing is a BST. The tree of Exercise 1(c) has the inorder walk 30, 60, 50, 70 and is rejected; a node compared only with its parent would have accepted it.
Exercise 7 · Counting comparisons — ex_bst.pyExBst.java. Implement insert, contains, path and height of a BST that counts one comparison per visited node. The tests check the counts against the walks of the video and the total cost n(n − 1)/2 of inserting 1, 2, …, n in order.
Solution
Reference code: solutions/py/ex_bst.py, solutions/java/ExBst.java. insert and contains follow the same path from the root, adding 1 to comparisons for every visited node; the first insert into an empty tree visits nothing, and a duplicate is detected at the visited node, so it costs the same as the successful search. path records the visited keys, so len(path(k)) equals the comparisons of one contains(k). The total for sorted insertion: the k-th insertion (k ≥ 2) visits all k − 1 existing nodes (every key is larger than everything in the tree, so the walk goes right all the way down the chain), so inserting 1, …, n costs 1 + 2 + … + (n − 1) = n(n − 1)/2 comparisons, the pair count of chapter 1; for n = 1,000 that is 499,500. The tree is a chain of height n − 1, and finding n afterwards costs n comparisons.
Exercise 8 · Delete — ex_delete.pyExDelete.java. Implement delete in the three cases (leaf, one child, two children through the in-order successor) and, as a final milestone, without recursion. The tests check that the tree stays a BST on random sequences, that the root is re-pointed correctly, and that 60 becomes the new root when 50 is deleted from the tree of video 3.
Solution
Reference code: solutions/py/ex_delete.py, solutions/java/ExDelete.java. A loop walks down remembering the parent (None / null for the root). If the node was not found, return False. In the two-children case, find the successor by going right once and then left as far as possible (remembering its parent), copy its key into the node, and continue with the successor as the node to remove; it has no left child (otherwise we could go further left), so it has at most one child. Now both remaining cases are one: the node has at most one child; re-point parent.left, parent.right or the root (when parent is None) to that child, which may be empty. Subtract 1 from size. Special cases the tests probe: the root with one child (the root pointer changes), the successor being the right child itself (then it is parent.right, not parent.left, that must be re-pointed), and the chain (the loop version needs O(1) memory; a recursive version needs one frame per level). The cost is one path, O(h).
READ THE CODE
An AI assistant wrote each function together with a claim. In Exercise 9 the code is wrong; in Exercise 10 the code is right and the claim is wrong. Find the error, give a small input that shows it, state the real behaviour and complexity, and say how to fix it. Use the habits from the chapter: test sorted input, count comparisons, check the ordering invariant after every operation.
Exercise 9 — delete in read/py/ex_read.py / ExRead.delete in read/java/ExRead.java. The comment claims it is correct and O(h).
Solution
The bug. In the branches key < node.key and key > node.key the result of the recursive call is thrown away: delete(node.left, key) instead of node.left = delete(node.left, key). The function returns node unchanged, so a node that the recursive call "removed" by returning None or its only child is never unlinked from its parent. What it does. (1) A leaf or one-child node below the root is not removed at all: from the tree 50 / (30 / (20, 40), 70 / (60, 80)), deleting 20 returns the same tree. The smallest failing input has two nodes: root 1 with the right child 2; delete(root, 2) leaves 2 in the tree. (2) The two-children case copies the successor's key into the node and calls node.right = delete(node.right, successor.key), which does store the result of that call; so the case "works" when the successor is the right child itself (deleting 30 from the tree above gives 20, 40, 50, …), and when it works at a node below the root it works only because the key is overwritten in place. But when the successor lies deeper (deleting 50), the recursive call reaches it through a discarded branch: the key 60 is copied to the root and the old 60 stays: the walk reads 20, 30, 40, 60, 60, 70, 80. (3) A root that is a leaf or has one child is handled correctly. That is why tests that only delete the root of a tiny tree pass and the bug survives. Real complexity of the code as written: still O(h) time, but it is the cost of a function that does not do its job. Fix: store what the recursive call returns, node.left = delete(node.left, key) and node.right = delete(node.right, key) (and the caller must write root = delete(root, key)). After the fix the tests of solutions/py/test_ex_read.pyExReadTest.java (theRepairIsCorrect) show the right result for every key of the example. The habit that finds it: after every operation check the ordering invariant and compare with a reference (sorted(list) / TreeSet) on random operations; and test deletion of every key of a small tree, not only the root.
Exercise 10 — contains in read/py/ex_read.py / ExRead.contains in read/java/ExRead.java. The comment claims O(h).
Solution
The error. The code returns the right answers but never uses the ordering: it searches the left subtree and the right subtree (contains(left) or contains(right)). That is a plain tree search, a preorder walk that stops at the first match. Real cost: a failed search visits every node, Θ(n); a successful search visits every node that comes before the key in preorder, up to n. On the 7-node tree of video 2, searching for 45 visits all 7 nodes where the real search visits 3 (50, 30, 40); the test counts these visits. The answers are right, so a correctness test cannot catch it; the doubling test does: in perfect trees of size 2ᵏ − 1 the correct search for an absent key visits k nodes, this one 2ᵏ − 1. (On a chain, both versions visit n nodes for the last key, since h = n − 1; this is not the case that shows the difference.) Fix: use the comparison to choose one side, if key < node.key: return contains(node.left, key) else contains(node.right, key), or write it as the loop of video 2. The cost is then O(h) (log n only for a balanced tree). The habit that finds it: count the nodes visited rather than timing, on a tree where h is much smaller than n, and compare with the length of the search path.