Stern–Brocot Rational Tree

The Stern–Brocot tree is a beautiful mathematical structure that enumerates all positive rational numbers in lowest terms. It generates these fractions by continuously forming the mediant of adjacent bounds, starting with 0/1 and 1/0.

worked-example

Finding the path for the target fraction 2/3.

Start with left bound L = 0/1, right bound R = 1/0. The current mediant is 1/1.
Compare 2/3 with 1/1. Since 2/3 < 1/1, we update our right bound R to 1/1 and append "L" to our path.
Next, our left bound is L = 0/1 and right bound is R = 1/1. The new mediant is (0+1)/(1+1) = 1/2.
Compare 2/3 with 1/2. Since 2/3 > 1/2, we update our left bound L to 1/2 and append "R" to our path.
Now L = 1/2 and R = 1/1. The new mediant is (1+1)/(2+1) = 2/3.
We have reached the target! The search completes, yielding the path "LR" to reach 2/3.

experiment

Explore different rational targets and trace their location in the Stern-Brocot Tree.

Set the Target dropdown to "5/7". Note the sequence of mediants evaluated as the search goes Left, Right, Right, Left.
Adjust the Depth limit. If you lower it below the number of steps required to reach the target, the search stops early, and "Found" displays "No".

Try it out here: https://riano.app/module/stern-brocot-rationals

limitations

This visualization only explores positive rational numbers up to a specified finite depth. Searching for fractions with very large numerators and denominators may require a depth exceeding the available UI choices, though the mathematical tree is infinite and covers all positive rationals.

references

The concepts demonstrated here rely on established properties of the Stern-Brocot tree.

Cut-the-Knot: Stern-Brocot Tree

Stern–Brocot Rational Tree