The Rational
3
5
= 0.6
Position
n
42
Tree level
5
Path from Root
LRLRL
Reading the path tells you how to reach this node from 1/1 at the root.
Binary Encoding
101010
Position n in binary. 0 = left, 1 = right. Skip the leading 1.
Run-Length → Continued Fraction
[1; 2, 3]
Count consecutive 0s and 1s. Each run length becomes a term in the continued fraction.
The Magic
Position 42 = binary 101010. Runs: 1,1,1,1,1,1. Continued fraction [1;1,1,1,1,1] = 8/5. The 42nd position in breadth-first order contains exactly the fraction 8/5.
How it works: The Calkin-Wilf tree starts with 1/1 at position 1.
Each node p/q has left child p/(p+q) and right child (p+q)/q.
Every positive rational appears exactly once. The position in breadth-first order
encodes the path as binary, and the run-length encoding of that path gives
the continued fraction of the rational. Integers secretly map to fractions.