Stern-Brocot Tree
Every positive rational number appears exactly once in the Stern-Brocot tree. Starting from the boundaries 0/1 and 1/0, each node is the mediant of its neighbors: (a+c)/(b+d) from a/b and c/d. Click nodes to expand the tree, or enter a decimal to watch the algorithm navigate to its fraction. The path from root to any node encodes its continued fraction representation.
mediant(a/b, c/d) = (a+c)/(b+d) · Path La0Ra1La2… ↔ [a0; a1, a2, …]
The mediant construction
The Stern-Brocot tree is built by a remarkably simple rule. Begin with the “boundary fractions” 0/1 on the left and 1/0 on the right (where 1/0 represents infinity). The root of the tree is their mediant: (0+1)/(1+0) = 1/1. For each node a/b, its left child is the mediant of a/b with its left ancestor, and its right child is the mediant of a/b with its right ancestor. This process produces every positive rational number exactly once, and always in lowest terms — the fraction a/b appears with gcd(a,b) = 1.
Connection to continued fractions
The path from the root to any fraction in the Stern-Brocot tree directly encodes its continued fraction expansion. If you go left a0−1 times, then right a1 times, then left a2 times, and so on, you trace the fraction [a0; a1, a2, …]. For example, the path to 3/5 is LLRL, meaning the continued fraction is [0; 1, 1, 2] — and indeed 0 + 1/(1 + 1/(1 + 1/2)) = 3/5. This connection means the Stern-Brocot tree is also a tool for computing best rational approximations to any real number.
Every rational appears exactly once
The proof uses the matrix representation. Each node can be associated with a 2×2 matrix with determinant 1. Going left multiplies by [[1,0],[1,1]] and going right by [[1,1],[0,1]]. Since these generate SL(2,Z) (up to sign), every pair of coprime positive integers (p,q) is reached by exactly one path, proving that every positive rational appears in the tree exactly once. The tree also has the binary search property: the left subtree of any node a/b contains only fractions less than a/b, and the right subtree only fractions greater.
History and applications
The tree was independently discovered by Moritz Stern in 1858 and Achille Brocot in 1861. Brocot was a French clockmaker who used the tree to design gear ratios — given a desired gear ratio (irrational number), the Stern-Brocot tree systematically finds the best rational approximation with bounded denominator. The tree also appears in the theory of Ford circles, Farey sequences, and the Calkin-Wilf tree (a closely related structure that enumerates rationals in a different order).