Function Repository Resource:

# SternBrocotTree

Generate a complete binary search tree of positive fractions

Contributed by: Ian Ford (Wolfram Research)
 ResourceFunction["SternBrocotTree"][n] generates a complete binary search tree of the positive fractions down to level n.

## Details and Options

The fractions on level d are those for which the total of the terms in its continued fraction representation is d+1.
In ResourceFunction["SternBrocotTree"][n], n can be any non-negative machine integer.
ResourceFunction["SternBrocotTree"] takes the same options as Tree.

## Examples

### Basic Examples (1)

Generate a complete binary search tree of the positive fractions down to level 4:

 In[1]:=
 Out[1]=

### Applications (1)

Approximate Pi as a rational number with a continued fraction representation with terms totalling 10:

 In[2]:=
 In[3]:=
 In[4]:=
 Out[4]=
 In[5]:=
 Out[5]=

### Properties and Relations (7)

gives the list of fractions in SternBrocotTree[n-1] between 0 and 1 with denominators not exceeding n:

 In[6]:=
 Out[6]=
 In[7]:=
 Out[7]=

SternBrocotTree gives a sorted binary tree, also known as a search tree:

 In[8]:=
 In[9]:=
 Out[9]=
 In[10]:=
 Out[10]=

A fraction with a continued fraction representation {a1,,ak} has children with continued fraction representations {a1,,ak-1,2} and {a1,,ak+1}:

 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

The fractions on level d are those for which the total of the terms in its continued fraction representation is d+1:

 In[13]:=
 Out[13]=

The fractions given by SternBrocotTree can be obtained by successively taking the sums of the numerators and denominators of consecutive pairs of fractions starting with 0 and Infinity:

 In[14]:=
 Out[14]=
 In[15]:=
 In[16]:=
 In[17]:=
 Out[17]=
 In[18]:=
 Out[18]=
 In[19]:=
 Out[19]=
 In[20]:=
 Out[20]=
 In[21]:=
 Out[21]=

The convergents of a positive fraction are a subset of its ancestors in the Stern-Brocot tree:

 In[22]:=
 Out[22]=
 In[23]:=
 Out[23]=
 In[24]:=
 Out[24]=

If , , , are the fractions at level d, then :

 In[25]:=
 Out[25]=
 In[26]:=
 Out[26]=
 In[27]:=
 Out[27]=

Define a function that permutes the positions on level d by reversing the corresponding binary integers with d digits:

 In[28]:=

Permute the fractions on each level of a Stern-Brocot tree:

 In[29]:=
 In[30]:=
 Out[30]=

The result is a Calkin-Wilf tree:

 In[31]:=
 Out[32]=

## Version History

• 1.0.0 – 06 January 2023