The Stern-Brocot tree is a binary search tree where the two legs represent "less than" and "more than" (or Low,High or Left,Right, etc).

As you can see from the image, it starts with 1 (or 1/1) at the top. The left side is less than 1 and the right side is more than 1. Once you choose a side; its' children are then less/more than that node.

Ok, that looks cool -- but what can we do with it?

We can use it to make a simple continued fraction for any positive number (decimal, fraction or whole number). We could probably expand it to handle negative numbers by starting at 0 instead of 1, but then we'd have to revisit the division-by-zero post.

The simple continued fraction is simply the continued fraction that has a '1' for all the partial numerators. Let's look at a simple example of how we can convert a decimal number into a continued fraction through use of the Stern-Brocot tree.

For this example, let's start with a simple decimal... Let's say,

*.*

**1.25**To convert the decimal to the SB tree, we'll walk down the tree and record our chosen path with 'L' for left and 'R' for right.

We start with the 1/1. Since 1.25 > 1/1, we choose the

*ight side of the tree.*

**R**Next choice: Since 1.25 < 2/1, we choose the

*eft path.*

**L**Next, 1.25 < 3/2, so again we choose the

*eft path.*

**L**Next, we chose

*eft for 1.25 < 4/3.*

**L**Last, we choose

*eft for 1.25 = 5/4 and we are done.*

**L**So, in order, we chose RLLLL.

We could also write that we chose R

^{1}L

^{4}.

But how do we translate that to a continued fraction? We just use the exponents!

R

^{1}L

^{4}becomes [1;4].

*Note: If we were using a number lower than 1 as our target, we'd put a '0' in front of that (like [0;1,4] which is actually the inverse; or 4/5).*

The process is easily reversible as well. Let's say we started with that Continued Fraction of [1;4].

First, we need to know whether to start with Left or Right. If the first digit is 0, choose Left; otherwise choose Right. So, for [1;4] we choose

**R**ight.

We remember that the number are the exponents; and that it will always alternate. So [1;4] becomes R

^{1}L

^{4 }.

The exponents represent a count of how many of that letter to choose; so that becomes [R][LLLL] or RLLLL.

Walking down the SB tree, we choose in order: 1/1, 2/1, 3/2, 4/3, 5/4.

Ok, that is all well and good... but that tree only shows a few rows; what do we do when it runs out?

The process for generating the next row isn't so bad when you see it paired with the continued fractions.

Below 5/4 for example:

5/4 = [1;4]

assuming that is in the form [a0;a1,a2,...,ak] the two children are:

[a0;a1,a2,...,ak+1] on the left and [a0;a1,a2,....,ak-1,2] on the right

Or in our particular case:

[1;4+1] = [1;5] = 6/5 = 1.2 on the left

[1;4-1,2] = [1;3,2] = 9/7 = 1.2857142857142858 on the right

and it is easy to verify that 1.2 < 1.25 < 1.2857...

or that 6/5 < 5/4 < 9/7

One more simple example in honor of 1:59 tomorrow....:

RRRLLLLLLLRRRRRRRRRRRRRRRLRRRRRRRRRRRRRRRRRRRRRRRRRLRRRRRRRLLLL

[3;7,15,1,25,1,7,4]

314159/100000 = 3.14159