Jason Davies

Calkin–Wilf Tree

The Calkin–Wilf tree contains every positive rational number exactly once.

Each vertex a/b has two children: (a+b)/b and a/(a+b).

Traversing the tree breadth-first results in the Calkin–Wilf sequence, depicted by the spiral below.

Further Reading

• Calkin–Wilf tree on Wikipedia.
• Recounting the Rationals, the original paper by Neil Calkin and Herbert Wilf.
• Recounting the Rationals, part I: a series of expository blog posts about the original paper on The Math Less Traveled. Highly recommended!
• Fractions on a Binary Tree II by A. Bogomolny.
• Enumerating the Rationals: some remarkable properties of the Calkin–Wilf sequence.