SternBrocot

The Stern–Brocot tree, often called SternBrocot, is an infinite binary tree that enumerates all positive rational numbers exactly once. It was independently discovered by Moritz Stern in 1858 and Achille Brocot in 1860 as a means of constructing a systematic list of fractions. The tree is built using the mediant operation: given two fractions a/b and c/d, their mediant is defined as (a+c)/(b+d). The construction begins with the root 1/1 and the two sentinel fractions 0/1 and 1/0 placed on either side. At each stage, the mediant of two adjacent fractions is inserted between them, creating a binary tree where each internal node’s children are the mediants of the node and its parent. Every positive rational appears exactly once in reduced form, and the depth of a fraction in the tree correlates with its complexity: simpler fractions reside near the root.

The Stern–Brocot tree has applications in number theory, computer science, and numerical methods. It provides an algorithmic way to generate all fractions, supports fast searching for a specific rational by following an L/R path determined by comparing the target to the current node, and yields properties of continued fractions. The tree also interplays with Farey sequences, as each level of the tree corresponds to the set of reduced fractions with denominators up to a given bound. Despite its simple construction, the Stern–Brocot tree offers a rich structure for exploring relationships among rational numbers and has been used in educational contexts and in the design of efficient data structures.