Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Stern–Brocot tree
open-in-new
<p>In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, the Stern–Brocot tree is an <a href="/facts/Binary_tree/TDV7GMpu">infinite complete binary</a> <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> in which the <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> correspond <a href="/facts/Bijection/ayC7YE3z">one-for-one</a> to the <a href="/facts/Positive_number/z0xollg1">positive</a> <a href="/facts/Rational_number/VJQmyY05">rational numbers</a>, whose values are ordered from the left to the right as in a <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a>. </p><p>The Stern–Brocot tree was introduced independently by <a href="/facts/Moritz_Stern/uqBPVNCJ">Moritz Stern</a> (1858) and <a href="/facts/Achille_Brocot/wssuWaWD">Achille Brocot</a> (1861). Stern was a German number theorist; Brocot was a French <a href="/facts/Clockmaker/ttytAgEW">clockmaker</a> who used the Stern–Brocot tree to design systems of gears with a <a href="/facts/Gear_ratio/znASyK8H">gear ratio</a> close to some desired value by finding a ratio of <a href="/facts/Smooth_number/pC6DVLJW">smooth numbers</a> near that value. </p><p>The root of the Stern–Brocot tree corresponds to the number 1. The parent-child relation between numbers in the Stern–Brocot tree may be defined in terms of <a href="/facts/Simple_continued_fraction/Wg1cMPxN">simple continued fractions</a> or <a href="/facts/Mediant_(mathematics)/AXo8Alrr">mediants</a>, and a path in the tree from the root to any other number q provides a sequence of <a href="/facts/Diophantine_approximation/WGVMuWF4">approximations</a> to q with smaller <a href="/facts/Denominator/ghnQE9B3">denominators</a> than q. Because the tree contains each positive rational number exactly once, a <a href="/facts/Breadth_first_search/2kulDXCx">breadth first search</a> of the tree provides a method of listing all positive rationals that is closely related to <a href="/facts/Farey_sequence/P6n10vaU">Farey sequences</a>. The left subtree of the Stern–Brocot tree, containing the rational numbers in the range (0,1), is called the Farey tree. </p>