Chapter 17. Binary Search Trees

Learning objectives

After this chapter you should be able to:

Do unaided:

Draw the binary search tree that a given sequence of inserts produces, and state its height.
Write insert, search and in-order traversal by hand, both recursively and with a loop.
Trace deletion in all three cases (leaf, one child, two children) on a drawing, and say which node is freed.
Explain why sorted input produces a tree of height n, and compute what that costs in comparisons and in stack frames.
Free a tree correctly, explain why the order must be post-order, and explain why recursion depth equals tree height.

May delegate:

Deletion, loop-based traversals and the move operations of stn::SensorIndex, written by a Writer agent from your header and checked by a Reviewer agent.
Generation of adversarial insert orders by a Tester agent, whose claims about tree height you verify by measurement.

Opening case

A composite case, not a real student or course.

Sam's PA6 team has three agent sessions open: a Writer, a Reviewer and a Tester. On Monday the Writer delivered stn::SensorIndex, a binary search tree that maps each sensor ID to that sensor's latest reading. Its summary was confident.

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Team phase.

PredictDraw the trees for the six-key orders of Section 17.2, predict heights for the six adversarial orders at n = 1,023, and predict the sorted-versus-random timing ratio at 10⁵, each with a confidence level.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 16 · Predict in Chapter 18 →
WriteInsert, search and in-order traversal by hand, recursively, with your own six-key test and drawings.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 16 · Write in Chapter 18 →
Specifysensor_index.hpp, the ownership rules (one owner per node; freeing never recurses), the complexity budget in terms of h, and the tests you require: random against std::set, all three delete cases, and a sorted tree deeper than Table 17.2.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 16 · Specify in Chapter 18 →
DelegateWriter implements erase, height, in-order and move from the header; Reviewer reads the diff for unlink paths and recursion; Tester generates adversarial orders without seeing the code.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Team Team phase: several agent sessions work in separate roles (Writer, Reviewer, Tester). You direct them and make the final call.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 16 · Delegate in Chapter 18 →
AuditASan and UBSan on all tests, Valgrind on a small run, Tester's heights against your predictions, the timing table against your derivation of O(log n) and O(n), and a keep-or-rewrite line for each function.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 16 · Audit in Chapter 18 →
DefendFive minutes: the height after a given order, the input that breaks a plain BST, and the line where each erased node is freed.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 16 · Defend in Chapter 18 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

A plain BST called "O(log n)" with no condition, tested only on random insert orders

How to catch it height() after a sorted insert; time random and sorted orders at three sizes ten times apart

Section 17.3.1 · Timing and log-log plots

A raw-pointer erase whose splice paths unlink a node without freeing it

How to catch it LeakSanitizer after erasing a leaf, a one-child node and a two-child node; owning links

Section 17.3.2 · LeakSanitizer

Recursion that follows the tree, including the implicit destructor chain of unique_ptr children

How to catch it A sorted tree deeper than Table 17.2's limit going out of scope under ASan: stack-overflow

Section 17.3.3 · AddressSanitizer

What the chapter covers

17.1 The concept, by hand
- 17.1.1 Why a tree
- 17.1.2 A node in memory
- 17.1.3 Recursion on trees, and a traced insert
- 17.1.4 Traversal
- 17.1.5 Height and balance
- 17.1.6 Delete: three cases
- 17.1.7 Freeing a tree: post-order
- 17.1.8 Recursion depth on a degenerate tree
- 17.1.9 The anchor: stn::SensorIndex
17.2 Predict and check
17.3 What agents get wrong here
- 17.3.1 Unbalanced trees on sorted input
- 17.3.2 Leaks in delete
- 17.3.3 Recursion depth on large trees
17.4 Working with the agent
17.5 Lab: Sensor index timing study
17.6 Defend it

Cost thread

The derivation comes first. A walk down the tree costs one comparison per level, so insert and find cost O(h). On sorted input the k-th insert walks past all k − 1 earlier nodes, so building the tree costs 0 + 1 + … + (n − 1) = n(n − 1)/2 comparisons, about 5 × 10⁹ for n = 10⁵. A successful search in the degenerate tree costs about n/2 comparisons on average. On random input both costs are proportional to log n. For n = 1,000 the gap is already large: the sorted build costs 1,000 × 999 / 2 = 499,500 comparisons, while a random build, where the average node depth is about 11 (Section 17.1.5), costs about 1,000 × 11 = 11,000, roughly 45 times fewer. Each tenfold increase in n multiplies the first number by 100 and the second by a little over 10, so the derivation predicts that the per-operation gap itself grows about tenfold per row of the table below.

Summary

In-order traversal of a BST visits keys in sorted order and checks validity, but says nothing about shape.
Insert, search and delete cost O(h); h lies between ⌈log₂(n + 1)⌉ and n, and insert order alone decides it: 2 to 2.5 times the minimum for random orders, n for sorted, reverse and zigzag, and 360 of 1,023 for a 98% sorted order.
Delete has three cases; with unique_ptr links, unlinking and freeing are one assignment, so the splice leak cannot be written.
Trees are freed in post-order, and any recursion that follows the tree, including the implicit unique_ptr destructor chain, goes as deep as the tree is tall: about 52,000 nodes crashed the book's build.
stn::SensorIndex uses owning links, loops, and a declared destructor that frees without recursion, with copy deleted and move written to match.
On sorted IDs cost per operation grew tenfold per tenfold n; AVL and red-black trees guarantee O(log n) height for every order, and std::map guarantees logarithmic lookup (libstdc++ uses a red-black tree).

Key terms

binary search tree (BST): a binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
leaf: a node whose left and right subtrees are both empty.
depth (of a node): the number of links from the root down to that node; the root has depth 0.
height (of a tree): the number of nodes on the longest root-to-leaf path; an empty tree has height 0.
traversal: a walk that visits every node of a tree exactly once.
in-order traversal: left subtree, node, right subtree; visits a BST's keys in increasing order.
pre-order traversal: node, then left subtree, then right subtree; used to copy a tree with its shape.
post-order traversal: left subtree, right subtree, then node; the order in which a tree must be freed.
in-order successor: the next larger key; for a node with a right subtree, that subtree's leftmost node.
degenerate tree: a tree in which every node has at most one child, so its height equals its number of nodes.
balanced tree: a tree whose height stays within a constant factor of log₂ n as keys are inserted and removed.
AVL tree: a self-balancing BST that keeps the heights of every node's two subtrees within one of each other.
red-black tree: a self-balancing BST whose coloring rules keep its longest root-to-empty-link path at most twice its shortest; the usual structure behind std::map, though the standard does not require it.
rotation: a local relinking of a parent and child that changes shape without breaking the ordering rule.

Companion code

16 files for this chapter, compiled with the book's flags.

Read the code Download ch17.zip

Connections

Where this chapter and another point to each other most often.

Chapter 3: Control Flow, Functions, Recursion, and Counting Operations
When that pointer is reset or destroyed, the node is freed at that moment, along with everything it owns. ### 17.1.3 Recursion on trees, and a traced insert Every subtree of a BST is itself a BST, so tree code is naturally recursive: act at the root, then do the same to one or both subtrees, with the empty tree as the base case (Chapter 3 introduced recursion and stack frames).
Chapter 14: Resource Ownership: RAII, the Rules of Zero, Three, and Five, and Smart Pointers
Each node owns its two children through std::unique_ptr (Chapter 14), so every node has exactly one owner: its parent's left or right link, or, for the root, the variable root.
Chapter 18: Hash Tables, Exceptions, and the Search Study
One honest caveat: growing pending allocates, and a destructor (like the noexcept move assignment that calls clear) cannot let an exception escape, so if that allocation ever failed the program would stop in std::terminate (Chapter 18).

See it on the map

17 Binary Search Trees