STERN-BROCOT every fraction, exactly once, no nodes stored
A binary tree that contains every positive fraction in lowest terms exactly once — built by taking mediants (a/b, c/d → (a+c)/(b+d)). The astonishing part for this corpus: it needs no stored nodes. You navigate it by comparison, computing each child on the fly — so it runs on plain numbers and dodges the pointer wall the other trees hit.
THE TECHNIQUE mediants, and a left/right address
Bracket a target between two fractions (start 0/1 and 1/0). Their mediant (numerators added, denominators added) is the node between them; compare it to the target and step left or right, tightening the bracket. The L/R turns spell the fraction’s address — and its continued fraction. Enter a fraction to see its path. live demo
HISTORY & CREDIT a number theorist and a clockmaker
“(a+c)/(b+d) is the wrong way to add fractions” — as addition, yes; as a mediant it is exactly right, and it generates every rational. cited
1858 · Moritz Stern studies the mediant tree in number theory — every positive rational appears once, already in lowest terms. 1861 · Achille Brocot, a Parisian clockmaker, rediscovers it to choose gear ratios — the best rational approximation with small teeth counts. the tie to Euclid · the L/R run-lengths of a fraction’s path give its continued fraction (the last run one short of the final term), and climbing back to the root is the subtractive Euclidean algorithm (dart 027). the Farey cousin · read level by level and it orders the rationals like the Farey sequence — mediants between neighbours.
3/5 = [0;1,1,2], path L R L — a number’s identity is its route through the tree. Stern 1858 / Brocot 1861
RECOMMEND FOR I-13 a tree that DODGES the pointer wall
The tree is infinite yet needs zero stored nodes — only four integers (the bracket) at any moment — and the descent runs on the compiler:
$ i13 run sb.i13 # descend to 3/5
depth = 4 # path L R L; mediants 1/1 -> 1/2 -> 2/3 -> 3/5
Recommend:nothing new — and pointedly so: where AVL (072), red-black (073), the trie (074) and the k-d tree (078) all hit PS-015 (heap-linked nodes), Stern-Brocot dodges it. A node’s identity is its L/R address, computed not stored; you hold four integers and take a mediant + one comparison per step (verified path to 3/5 at depth 4). It runs on plain scalars — no allocation, no pointers, no rotations. Note: it ties Euclid (027) directly — the path’s run-lengths give the continued fraction (last run one short of the final term), the parent is one subtraction. The only thing that reintroduces the wall is materialising a whole level; for point queries and best-rational-approximation, the corpus needs no node objects at all.