Calkin-Wilf tree: root=1/1. Left child of a/b is a/(a+b). Right child is (a+b)/b. Every positive rational appears exactly once! BFS order: 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4,... The n-th term b(n)/b(n+1) uses the Stern diatomic sequence.
How to Use
Enter fraction or index:
- Path: Binary path from root
- Index: Position in BFS
- Children: Left and right
Stern Connection
The n-th fraction in BFS order is b(n)/b(n+1) where b is the Stern diatomic sequence: b(0)=0, b(1)=1, b(2n)=b(n), b(2n+1)=b(n)+b(n+1). This connects the tree to hyperbinary representations.
vs Stern-Brocot
Both trees contain every positive rational once. Stern-Brocot uses mediants (sorted order). Calkin-Wilf uses simpler rules (not sorted). Calkin-Wilf was discovered in 2000; Stern-Brocot in 1858.
Step-by-Step Instructions
- 1Enter fraction.
- 2Find path.
- 3Browse levels.
- 4Compare to Stern-Brocot.
- 5Check index.