Definition
The Stern–Brocot tree is an infinite complete binary tree whose vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a binary search tree.

Sequence Construction

It’s easy to see the construction in just sequence form. We start with the very first two terms

\[ \frac{0}{1} \quad \text{and} \quad \frac{1}{0} \]

Then we add the mediant where if we’re given two fractions \(\frac{a}{b}\) and \(\frac{c}{d}\). Their mediant is simply

\[ \frac{a+c}{b+d}. \]

Hence we insert \(\frac{0+1}{1+0} = \frac{1}{1}\) in between \(\frac{0}{1}\) and \(\frac{1}{0}\) to get

\[ \frac{0}{1}, \quad \frac{1}{1}, \quad \frac{1}{0} \]

Repeat the same process. So now we will insert \(\frac{0+1}{1+1} = \frac{1}{2}\) and \(\frac{1+1}{1+0} = \frac{2}{1}\) in

\[ \frac{0}{1}, \quad \textcolor{red}{\frac{1}{2}}, \quad \frac{1}{1}, \quad \textcolor{red}{\frac{2}{1}}, \quad \frac{1}{0} \]

We repeat the process again and insert the mediant between every two fractions as follows

\[ \frac{0}{1}, \quad \textcolor{red}{\frac{1}{3}}, \quad \frac{1}{2}, \quad \textcolor{red}{\frac{2}{3}}, \quad \frac{1}{1}, \quad \textcolor{red}{\frac{3}{2}}, \quad \frac{2}{1}, \quad \textcolor{red}{\frac{3}{1}}, \quad \frac{1}{0} \]

Observe that in every iteration that the sequence is always ordered from left to right. Here is one more iteration:

\[ \frac{0}{1}, \quad \textcolor{red}{\frac{1}{4}}, \quad \frac{1}{3}, \quad \textcolor{red}{\frac{2}{5}}, \quad \frac{1}{2}, \quad \textcolor{red}{\frac{3}{5}}, \quad \frac{2}{3}, \quad \textcolor{red}{\frac{3}{4}}, \quad \frac{1}{1}, \quad \textcolor{red}{\frac{4}{3}}, \quad \frac{3}{2}, \quad \textcolor{red}{\frac{5}{3}}, \quad \frac{2}{1}, \quad \textcolor{red}{\frac{5}{2}}, \quad \frac{3}{1}, \quad \textcolor{red}{\frac{4}{1}}, \quad \frac{1}{0} \]

One way to implement this is the following:

int iterations = 1000;
std::vector<Fraction> sequence = {
    {0, 1},
    {1, 0}
};
for (int iteration = 1; iteration <= iterations; ++iteration) {
    std::vector<Fraction> next_sequence;
    // size of new sequence
    next_sequence.reserve(sequence.size() * 2 - 1);
    // for every pair, calculate the mediant
    for (std::size_t i = 0; i + 1 < sequence.size(); ++i) {
        const Fraction& left = sequence[i];
        const Fraction& right = sequence[i + 1];
        // the left parent
        next_sequence.push_back(left);
        // insert the mediant
        Fraction mediant = {
            left.numerator + right.numerator,
            left.denominator + right.denominator
        };
        // insert the right median
        next_sequence.push_back(mediant);
    }
    next_sequence.push_back(sequence.back());
    sequence = std::move(next_sequence);
}

Tree Construction

TODO…..

Search Example

TODO

References