Project 6 — A Searchable Tree

“He is like a tree planted by streams of water that yields its fruit in its season, and its leaf does not wither.” — Psalm 1:3

Chapter: 6 — Trees: When Hierarchy Is the Shape Due: End of Week 6 Submit: A link to a public GitHub repo containing bst.py, your test file, your benchmark script (Medium), MEMO.docx (Hard), and README.txt. Real toolchain, real git — see Appendix A for the Python + git setup. Allowed tools: Python 3.10+, the standard library (time, sys, collections, unittest/pytest), a real editor, the textbook. AI: Phase 1 (wk 1–8): AI is OFF. No assistants, no completion-beyond-a-word, no “explain this.” You cannot direct an agent to choose a tree over a hash later — or to pick a database’s index type in Phase 2 — if you have never built a tree, watched it degrade, and measured the cost yourself. The entire point of building it now is so that in Phase 2 you can direct an agent who writes CREATE INDEX and know whether it chose the right index type. Phase 2 (wk 9–16) turns agentic AI on and requires an agent-log.txt. Not yet.

The Setup

A growing ministry runs a Scripture-memory program. Hundreds of members are working through a memory plan, and each member’s progress is keyed by a verse number in a master numbering of the plan’s verses (verse 1 through verse N, assigned in plan order). The team needs a structure that answers four kinds of question fast:

1. Is member-facing verse #347 in the plan? — membership.
2. Give me every verse in the plan, in order, to render the printed booklet. — sorted iteration.
3. What’s the lowest-numbered verse nobody’s started yet? and the highest assigned? — min / max.
4. Show me verses #100 through #150 — this week’s section. — range query.

The lead developer’s first instinct was the hash table you built in Project 5. It nails question 1 — O(1) membership — and it utterly fails questions 2, 3, and 4, because a hash table throws away all order (§6.8). Rendering the booklet in order would mean collecting every key and sorting it (O(n log n)) on every render; “this week’s section” would mean scanning the entire table.

The four questions together describe a structure that keeps its keys ordered and still searches fast. That’s a binary search tree. You’re going to build it — insert, contains, delete (all three cases), and the in-order traversal that yields the booklet already sorted, for free — and then you’re going to measure what it costs and decide, in writing, when it (and not the hash table) is the right tool.

This is the exact decision a database makes when it chooses an index. You’re learning it by hand now so you can make it for real in Phase 2.

Learning Targets

By completing this project, you will demonstrate that you can:

• Implement a binary search tree with recursive insert and the reassign-the-link pattern.
• Implement contains and the three-case delete (leaf, one child, two children with the in-order-successor swap), preserving the ordering invariant.
• Implement an in-order traversal that yields keys in sorted order, and prove it with tests.
• (Medium) Implement min, max, height, and an O(log n + k) range query, and measure the lookup-cost gap between a balanced and a degenerate tree.
• (Hard) Write the architect’s memo comparing tree vs hash table by workload, tied to the database-index decision — the Phase 1 right-tool deliverable.

Normal Tier

Goal: Implement a correct BST of unique, comparable keys, with insert, contains, delete (all three cases), and an in-order traversal that yields sorted keys — with tests that prove every claim, including each delete case.

Required features

1. A BST class backed by _Node objects (key + left + right), with a _root and a tracked _size. No Python dict, set, sorted(), or list.sort() standing in for the tree — that defeats the project. The tree’s structure must be real nodes you link by hand.
2. Core operations:
   • insert(self, key) — recursive; ignore duplicates (set semantics); update _size only on a real insert.
   • contains(self, key) / __contains__ — return True/False; O(height).
   • delete(self, key) — remove if present; update _size; handle all three cases. Case 3 (two children) must use the in-order-successor key-copy method from §6.4 (do not rewire subtrees by hand).
   • in_order(self) — a generator (or returns a list) yielding every key in ascending sorted order.
   • __len__(self) — current size, O(1).
   • __iter__(self) — iterate in sorted order (delegate to in_order).
3. Invariant discipline. The ordering invariant (every left-subtree key < node key < every right-subtree key) must hold after every operation. Use strict < / >; handle equal as “found / already present.” (See §6.9 Common Bugs.)
4. Tests that prove the behavior (unittest or pytest):
   • Insert n keys (shuffled); len is the count of distinct keys; contains is true for each inserted key and false for one you didn’t insert.
   • In-order is sorted: insert a shuffled set and assert list(tree.in_order()) == sorted(distinct_keys).
   • Duplicate insert is a no-op: inserting the same key twice leaves len unchanged and the key present once.
   • Delete Case 1 (leaf): delete a leaf; assert it’s gone, len dropped by 1, and in-order is still sorted.
   • Delete Case 2 (one child): delete a node with exactly one child; assert the child’s subtree survived and in-order is still sorted.
   • Delete Case 3 (two children): delete a node with two children (and separately, the root with two children); assert the key is gone, every other key still present, and in-order is still sorted (the proof the successor swap preserved the invariant).
   • Delete absent key is a safe no-op (no crash, len unchanged).

Example output

A tiny driver (python3 bst.py) should be able to do this:

>>> tree = BST()
>>> for k in [50, 30, 70, 20, 40, 60, 80, 35, 45]: tree.insert(k)
>>> list(tree.in_order())
[20, 30, 35, 40, 45, 50, 60, 70, 80]
>>> 40 in tree
True
>>> 41 in tree
False
>>> tree.delete(20)            # leaf
>>> tree.delete(30)            # one child
>>> tree.delete(50)            # two children (root) -> successor 60 takes its place
>>> list(tree.in_order())
[35, 40, 45, 60, 70, 80]       # still sorted
>>> len(tree)
6

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. min, max, height, and a range query

Add:

• min(self) — smallest key (walk all the way left); raise ValueError on an empty tree.
• max(self) — largest key (walk all the way right); raise ValueError on an empty tree.
• height(self) — height of the tree (empty tree = -1, single node = 0). Bound the work to O(n).
• keys_between(self, lo, hi) — all keys in the inclusive range [lo, hi], in sorted order, with subtree pruning so it does not visit subtrees entirely outside the range (the §6.5 / Rep 10 version). Aim for O(log n + k) on a balanced tree.

Write tests for each, including: min/max on a known tree; height on a hand-built balanced tree (known answer) and a sorted-insert chain (height = n-1); keys_between returning a correct sorted slice, an empty result for a range with no keys, and the full set when lo/hi bracket everything.

M2. Measure balanced vs degenerate (the cost deliverable)

Write benchmark_balance.py. Build the same set of n keys (e.g. n = 20,000) two ways:

• Balanced-ish: insert in random/shuffled order.
• Degenerate: insert in sorted order.

Report, in a table, each tree’s height and the total time for a fixed batch of lookups (e.g. 20,000 random contains calls). You should see the degenerate tree’s height ≈ n and its lookups hundreds of times slower. (Watch the recursion limit — build/measure the degenerate tree iteratively, as code/balance_degradation.py does, or you’ll hit RecursionError.) Put the table in your README and write two sentences relating it to §6.6: the cost is O(height), not O(log n); the only thing that changed was insert order, and insert order decided the shape, and shape is cost. Name the fix (a self-balancing tree — AVL / red-black — guarantees height ≈ log n regardless of insert order); you are not asked to implement one.

Hard Tier (+up to 25% additional extra credit)

H1. Predecessor / successor

Add predecessor(self, key) and successor(self, key) — the largest key strictly less than key, and the smallest key strictly greater than key (return None if none exists). key need not be present in the tree. Test against the in-order sequence: for a sorted list of the tree’s keys, successor(k) is the next element after k, predecessor(k) the previous. These two operations are, with range query, the BST’s reason for existing over a hash table — and they’re what a database uses for cursor-style “next row” navigation.

H2. The tree-vs-hash benchmark

Write benchmark_tree_vs_hash.py that puts your BST against your HashMap from Project 5 (import it, or paste a copy) on the same n keys, timing four workloads:

For the hash table’s “sorted iteration,” “min/max,” and “range,” you must implement them the only way a hash can — collect all keys and sort/scan — and time that honestly. Produce a results table. The numbers should make §6.8 undeniable: hash wins membership; the tree wins everything that needs order.

H3. The architect’s memo (the judgment piece)

Write MEMO.docx (half a page to a page). This is the heart of the Hard tier and the deliverable an agent cannot write for you, because it requires judgment about which cost matters under which constraint. Using your own measured numbers from H2:

1. State the rule in your own words: when is the tree the right tool, and when is the hash? Tie it to your measured numbers (which workload each won, and by how much).
2. The four ministry questions from The Setup: for each (membership, sorted booklet render, min/max-unstarted, this-week’s-section range), say which structure serves it and why. Then decide: for this application as a whole, which one structure would you build on, given that you need all four? Defend the choice. (Hint: if even one workload needs order, the hash alone can’t serve it — but you could also keep both. Name the cost of keeping both.)
3. The database-index link. Explain, in two or three sentences, how this exact decision recurs in Phase 2 when you choose a database index: a hash index gives O(1) exact-match lookup and cannot do BETWEEN / ORDER BY / MIN / MAX; a B-tree index (a balanced search tree, the default in SQLite/Postgres) does both. State which index type you’d put on the verse-number column given the four queries above, and why. (You’re choosing tree-vs-hash again, on a structure the database builds for you — §6.8.)
4. Name the constraint that would flip your answer. Under what realistic change in the application’s query patterns or scale would you switch your recommendation?

This memo is the architect’s actual work. The benchmark numbers are necessary; the judgment about which number matters under which constraint is the part no tool does for you, and it’s exactly why Phase 1 makes you build and measure before Phase 2 lets you delegate.

Submission

Submit one URL: a public GitHub repo.

What the repo must contain

1. bst.py — the BST class, with the example driver under if __name__ == "__main__":.
2. test_bst.py — your tests (Normal-tier proofs at minimum; M1 operations for Medium; H1 for Hard). Confirm they pass before submitting (python3 -m pytest or python3 -m unittest).
3. benchmark_balance.py (Medium) and benchmark_tree_vs_hash.py (Hard) — runnable measurement scripts.
4. MEMO.docx (Hard) — the tree-vs-hash architect’s memo.
5. README.txt — your reflection:

# Project 6 — A Searchable Tree

**Tier targeted:**  Normal / Medium / Hard
**Features done:**  (list)
**Delete Case 3 in my own words:**  (two sentences — the successor key-copy)
**Why in-order yields sorted keys:**  (one sentence)
**Measured balanced vs degenerate:**  (paste your Medium table if applicable)
**Tree-vs-hash measurements:**  (paste your Hard table if applicable)
**Right-tool rule:**  (one line; full reasoning in MEMO.docx)
**What I learned:**  (one paragraph)
**What I'd change:**  (one sentence)
**AI usage:**  NONE — Phase 1.  Signed: <your name>

6. Reflection comment block at the top of bst.py — same fields as the README, condensed.
7. The code left runnable — python3 bst.py runs the driver without errors.

Hints (Read Before You Begin)

• Draw the three delete cases before you write delete. On paper, three small trees, three results (§6.4 and Rep 7). Every delete bug is a bug you’d have seen in the drawing. Don’t code delete until you can draw all three from memory.
• Reassign the link, every time. node.left = self._insert(node.left, key) — never discard the return value. This one habit prevents the single most common tree bug (§6.9). Type it until it’s automatic.
• Case 3 = copy a key, don’t move nodes. Find the in-order successor (smallest key in the right subtree — walk left until you can’t), copy its key into the node you’re “deleting,” then delete the successor from the right subtree. The successor has no left child, so its deletion is the easy Case 1/2. Resist the urge to rewire subtrees.
• In-order = left, me, right. If your in-order output isn’t sorted, either the tree is built wrong (check insert) or you swapped the order of the three statements. The sorted-ness of in-order is your built-in correctness check — assert it after every delete in your tests.
• Mind the recursion limit on degenerate trees. A sorted-insert tree has height = n; recursing on it n deep crashes (RecursionError). For the Medium/Hard benchmarks, build and walk the degenerate tree iteratively (see code/balance_degradation.py). This crash is the §6.6 lesson arriving in person — note it, then work around it.
• Time with time.perf_counter(), run more than once, report the median. The first run is cold; disable any printing inside the timed loop — printing dominates the measurement.

What Mastery Looks Like (Beyond the Rubric)

A great Project 6 has a delete you can read in thirty seconds and immediately see all three cases: leaf and one-child collapse into two lines, and Case 3 is “copy the successor’s key, delete the successor” — no pointer gymnastics, no special-casing the root. The tests don’t just check that it works; they prove the invariant survives: every delete test ends by asserting in-order is still sorted, which is the one assertion that catches a broken Case 3.

A great Medium tier produces a balanced-vs-degenerate table that makes §6.6 undeniable — same keys, height 30 vs height 20,000, lookups hundreds of times slower — and two sentences that name the cause (cost is O(height); insert order decided the shape) without hand-waving.

A great Hard tier produces a memo a real engineer would nod at. It doesn’t just say “tree is better.” It says: hash wins membership by this measured margin; tree wins sorted iteration, min/max, and range by these margins; for this application, which needs all four, I’d build on the tree (or keep both, at this cost) — and this is the same call I’ll make in Week 11 choosing a B-tree index over a hash index on the verse-number column, for exactly these reasons. That last sentence — connecting the structure you built by hand to the database decision you’ll make later — is the architect’s sight the whole book is training.

Coach’s Note — Students are tempted to skip the memo and let the code carry the grade. Don’t. The code proves you can build a tree; the memo proves you can choose one — and choosing is the job that survives the arrival of AI. An agent will write you a flawless BST in five seconds in Phase 2. It will not tell you whether your application’s query patterns deserve a tree or a hash, because that’s a fact about your problem, not the model’s training. The memo is where you become the architect instead of the prompt.

When You’re Done

1. Run python3 bst.py. Confirm the driver prints sorted in-order before and after the three deletes.
2. Run your tests. All green. Then deliberately break Case 3 — make it copy the predecessor from the left subtree but delete from the right subtree (a classic mismatch) — re-run, and watch the in-order-sorted assertion fail loudly. Restore. This is Coding 2’s red-green discipline applied to a structural invariant.
3. (Medium) Run benchmark_balance.py, paste the table into your README, write the two sentences.
4. (Hard) Run benchmark_tree_vs_hash.py, write MEMO.docx, make the index-type recommendation.
5. Read your own delete slowly. Could a stranger see all three cases and the successor swap from the code alone? If not, simplify.
6. Commit, push, submit the repo URL.
7. Read Chapter 7. Graphs next — where the queue-driven breadth-first search you wrote for level-order this week becomes the engine for shortest paths, and a tree is revealed as just a graph with no cycles and one root.

A theological footnote. The psalmist’s tree is fruitful because it is planted by streams of water and rooted — every leaf it grows is fed through an unbroken connection to its source (Psalm 1:3). The vine says the same of its branches: “apart from me you can do nothing” (John 15:5). Your binary search tree is a small, mechanical echo of that truth — every node holds its place, and the whole structure bears its fruit (sorted order, fast search, range queries), only because the connection back to the root holds unbroken. When you wrote delete carefully — copying a key instead of carelessly severing a branch and orphaning everything below — you were tending a living shape rather than blanking a slot. That care is the same care the church takes with what abides and what is pruned. Build trees that abide. Steward the connection.

See you next week.