A Calkin-Wilf tree is a special type of binary tree obtained by starting with the fraction 1/1 and iteratively adding a/(a + b) and (a + b)/b below each fraction a/b. The Stern-Brocot tree is closely related, putting a/(a + b) and b/(a + b) below each fraction a/b. Both trees generate every rational number. Writing out the terms in sequence gives 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, ...The sequence has the property that each denominator is the next numerator. This sequence, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (OEIS A002487), is known as Stern's diatomic series, or the fusc function.

binary tree | Stern-Brocot tree | Stern's diatomic series