Editing Euclidean algorithm (section)

=== Stern–Brocot tree ===
{{main|Stern–Brocot tree}}
The Euclidean algorithm can be used to arrange the set of all positive [[rational number]]s into an infinite [[binary search tree]], called the [[Stern–Brocot tree]].
The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number ''a''/''b'' can be found by computing gcd(''a'',''b'') using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether ''a''/''b'' is given in lowest terms, and forms a path from the root to a node containing the number ''a''/''b''.<ref>{{cite book|title=Concrete mathematics|page=123|author1-link=Ronald Graham|last1=Graham|first1=R.|author2-link=Donald Knuth|last2=Knuth|first2=D. E.|author3-link=Oren Patashnik|last3=Patashnik|first3=O.|publisher=Addison-Wesley|year=1989}}</ref> This fact can be used to prove that each positive rational number appears exactly once in this tree.

For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:
[[Image:SternBrocotTree.svg|thumb|400px|The Stern–Brocot tree, and the Stern–Brocot sequences of order ''i'' for ''i'' = 1, 2, 3, 4]]
: <math> 
\begin{align}
 & \gcd(3,4) & \leftarrow \\
= {} & \gcd(3,1) & \rightarrow \\
= {} & \gcd(2,1) & \rightarrow \\
= {} & \gcd(1,1).
\end{align}
</math>

The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the [[Calkin–Wilf tree]]. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.