SternBrocot tree is a tree data structure whose vertices correspond to the set of nonnegative rational numbers. Thus, this tree provides a very elegant way for constructing the set of fractions m/n
, where m
and n
are relatively prime. To construct the tree, the basic idea is to start with two fractions (0/1
, 1/0
) and then repeat the following operation:
Insert (m+m’)/(n+n’) between two adjacent fractions m/n and m’/n’
The first step gives us the entry 1/1
between 0/1
and 1/0
. Similarly, the 2nd step gives us two more: 0/1
, 1/2
, 1/1
, 2/1
, 1/0
.
Continuing on like this results in an infinite binary search tree which preserves the usual ordering of rational numbers.
The figure below shows the 1st 4 levels of the SternBrocot tree.
The first 4 levels of SternBrocot Tree
Finding the Path to k in SternBrocot Tree
The path from the root of the tree to a number k
in the SternBrocot tree can be found using binary search. At each node, k
will either be in the left half of the tree, or the right half. We continue down the left or right subtree until we finally find k
.
 Initialize the left fraction
L
to0/1
and right fractionR
to1/0
 Repeat the following until
k
is found: Compute the mediant
M
(which is(m+m')/(n+n')
)  If
(k>M)
, thenk
is in the right half of the tree.L:=M
and continue.  Else If
(M>k)
, thenk
is in the left half of the tree.R:=M
and continue.  Else
k=M
, terminate search.
 Compute the mediant
Implementation
There’s a couple of things to tackle in our implementation. First, I need an easy way to represent fractions, so I create my own SternBrocotFraction
class. I deliberately chose to make it very specific to this algorithm because I needed a special way to handle the fraction 1/0 (which by definition is greater than all other rationals).
Secondly, I needed a good way to represent the path from the root of the tree to k. I do this by using a StringBuilder
, and at each step I append either the letter L
or R
depending on which subtree we take. When the search is finished, this gives us a string representation of the path from the root of the tree to the number k
. This approach is similar to the approach advocated by ACM Programming Competitions for the “SternBrocot Number System” problem.
Here’s the code to find path to a number k:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 

The special SternBrocotFraction
class is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 

Finally, some test code to exercise my class:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
