The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. But it is not obvious how to construct a list that is sure to contain every rational number precisely once. In a previous post we described the Farey Sequences. Here we examine another, related, approach.
The Stern-Brocot Tree
We consider a tree structure that contains each positive rational number precisely once. It was devised independently by Moritz Stern, a German number theorist and Achille Brocot, a French clockmaker. Brocot was interested in designing gear systems with specific gear ratios, constrained by engineering practicalities.
We start with two boundary values, to represent
and
to represent
. They are not members of the tree, but are used to generate new entries by forming mediants. Recall that the mediant of two rational numbers
and
is
and its value always falls between the two numbers.
The root of the tree is , which is the mediant of the boundary values. Thus, at Level 1 we have three numbers
. This is the first Stern-Brocot sequence. To construct a new level, we form the mediant of each adjacent pair of ratios in the level above. Thus, if there are
entries at level
, there are
new entries at Level
. If we now carry down the
numbers at Level
to Level
, we get the
st Stern-Brocot sequence, which has
entries. This is then used to generate the new entries of the sequence at Level
.
If we include only new entries at each level, we see that all rationals can be included in a tree structure (see Figure below), and each rational occurs precisely once. Every branch of the tree bifurcates at every level. Each number in the tree has two “children” but only one “parent”. For a rational , the left child is smaller than
while the right child is greater. Explicit values for the children can be expressed in terms of continued fractions.

The Stern-Brocot tree and Stern-Brocot sequences of order n for n from 1 to 4. [ Image from Wikimedia Commons].
For comparison, the 4 Farey sequence is
The process of generating the Stern-Brocot tree has some similarity to that used to generate the Farey sequences. But, at each stage, all the mediants are included, not only those having a specific value of the denominator. Moreover, the Stern-Brocot tree includes all positive rationals, not just those in the interval .
Stern-Brocot sequences of orders 1 to 4, arranged to show new entries at each stage.
The Calkin-Wilf Tree
In a following article, we will introduce another structure, the Calkin-Wilf Tree. It is quite similar to the Stern-Brocot tree, but the differences are interesting.
Sources
Wikipedia article Stern-Brocot Tree.