Stern-Brocot Tree


A special type of binary tree obtained by starting with the fractions 0/1 and 1/0 and iteratively inserting (m+m^')/(n+n^') between each two adjacent fractions m/n and m^'/n^'. The result can be arranged in tree form as illustrated above. The Farey sequence F_n defines a subtree of the Stern-Brocot tree obtained by pruning off unwanted branches (Vardi 1991, Graham et al. 1994).

See also

Binary Tree, Calkin-Wilf Tree, Farey Sequence, Ford Circle, Stern's Diatomic Series

Explore with Wolfram|Alpha


Bogomolny, A. "Stern-Brocot Tree.", A. "Calcul des rouages par approximation, nouvelle méthode." Revue Chonométrique 3, 186-194, 1861.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 116-117, 1994.Haynes, B. "On the Teeth of Wheels." American Scientist 88, No. 4, July-August 2000., M. A. "Über eine zahlentheoretische Funktion." J. reine angew. Math. 55, 193-220, 1858.Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, p. 253, 1991.Viswanath, D. "Random Fibonacci Sequences and the Number 1.13198824...." Math. Comput. 69, 1131-1155, 2000.

Referenced on Wolfram|Alpha

Stern-Brocot Tree

Cite this as:

Weisstein, Eric W. "Stern-Brocot Tree." From MathWorld--A Wolfram Web Resource.

Subject classifications