In earlier lessons this is where transit — the Vilnius public-transport journey planner — supplied real numbers.

Not in this lesson, because transit contains no tree at all. Verified: every named type in the repository was checked, and there is no BST, no AVL, no red-black tree, no left/right fields anywhere. The only tree-shaped types are byteNode and runeNode, and those are the prefix tries from lesson 10 — they branch on a letter, not on a comparison, and hold no ordered set.

So that is what gets said, rather than reaching for something adjacent.

What it uses instead, though, is interesting

transit needs exactly what this lesson built a tree for: find the first element not smaller than a given one. "What is the next departure after 8:15?"

Its answer is a sorted slice and a binary search, not a tree:

func (b *BinaryDepartureIndex) NextDeparture(stopID string, afterSec int32) (int32, bool) {
	times := b.d.byStop[stopID]
	i := lowerBound(times, afterSec)
	if i == len(times) {
		return 0, false
	}
	return times[i], true
}

That is lesson 6's lowerBound — the same one you wrote there.

Why that is enough for it and not for you

There is one difference, and it decides everything.

Departures is built once, in LoadDepartures: the rows are read from the database, each stop's slice is sorted, and it is never modified again. The byStop field is unexported and no method writes to it.

When that is true, a sorted slice wins on every axis:

	sorted slice	BST
lookup	O(log n), perfectly balanced for free	O(log n) with a worse constant
ordered output	already ordered	a traversal
range	two binary searches and a slice	a pruned traversal
memory	no pointers, contiguous, cache-friendly	+2 pointers per node, scattered
insertion	O(n) — the whole tail shifts	O(log n)

The last row is the entire story. A tree pays for the ability to insert into it after it has been built. If your data is loaded once and only read afterwards, that price buys nothing — take the slice.

Your library is not like that: Put can be called at any time. Hence the tree.

And hence step 7 is a real problem: precisely because the shape depends on insertion order, the insertion order can ruin it.