A Calkin-Wilf tree is a special type of binary tree obtained by starting with the fraction 
and iteratively adding 
and 
below each fraction 
. The Stern-Brocot tree
is closely related, putting 
and 
below each fraction 
. 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 (Dijkstra 1982).
| CARVIEW |
Select Language
HTTP/2 200
date: Sat, 17 Jan 2026 19:19:27 GMT
server: Generic Web Server
set-cookie: WR_SID=7cead82b.6489a561a8af5; path=/; max-age=315360000; domain=.wolfram.com
accept-ranges: bytes
content-type: text/html; charset=UTF-8
content-security-policy: upgrade-insecure-requests
Calkin-Wilf Tree -- from Wolfram MathWorld
TOPICS
TOPICS
Calkin-Wilf Tree
See also
Binary Tree, Stern-Brocot Tree, Stern's Diatomic SeriesExplore with Wolfram|Alpha
More things to try:
References
Bogomolny, A. "Fractions on a Binary Tree II." https://www.cut-the-knot.org/blue/Fusc.shtml.Calkin, N. and Wilf, H. S. "Recounting the Rationals." Amer. Math. Monthly 107, 360-363, 2000.Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective. New York: Springer-Verlag, pp. 215-232, 1982.Gibbons, L.; Lester, D.; and Bird, R. "Functional Pearl: Enumerating the Rationals." J. Func. Prog. 16, 281-291, 2006.Schneider, K. "The Tree of All Fractions." https://demonstrations.wolfram.com/TheTreeOfAllFractions/.Sloane, N. J. A. Sequence A002487/M0141 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Calkin-Wilf TreeCite this as:
Weisstein, Eric W. "Calkin-Wilf Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Calkin-WilfTree.html