# Recursive Stern-Brocot tree definition

I am trying to build a Stern-Brocot tree (enumeration of rationals).

The result is nearly acceptable, but I am still dissatisfied with the following points.

1. The edge from the parents goes to the middle of the child node, not the upper border.
2. The command does not (re)evaluate it's arguments at each iteration (we keep 1+1+1 instead of 3)
3. I cannot use \bt@n and \bt@d in the recursive calls, as they are somehow messed up (why ?).
4. I have to give a name to my nodes, which is useless, but LaTeX won't compile without.

Here is the code :

\documentclass{standalone}
\usepackage{tikz}
\usepackage{etoolbox}

\newcommand{\eval}[1]{\pgfmathparse{int(#1)}\pgfmathresult}

\makeatletter  % We can use the @ symbol in macro names
\def\mybtree#1#2#3#4#5{%

\pgfextra{ % Allows us to use non-drawing commands
\pgfmathtruncatemacro\bt@depth{#5}    % Current depth
\pgfmathtruncatemacro\bt@ndepth{\bt@depth - 1}  % Next depth

\pgfmathtruncatemacro\bt@n{#1+#3}
\pgfmathtruncatemacro\bt@d{#2+#4}

%% Calculate the sibling distance
%  distance = 2^{remaining depth}
\pgfmathsetmacro\bt@sdistance{pow( 2, \bt@depth)}
}

node (\bt@n/\bt@d) {$\frac{\eval{#1+#3}}{ \eval{#2+#4}}$}

\ifnumgreater{\bt@depth}{0}{% if( depth > 0 ) then:
child [sibling distance=\bt@sdistance*2em] {
\mybtree{#1}{#2}{#1+#3}{#2+#4}{\bt@ndepth}
}
child [sibling distance=\bt@sdistance*2em] {
\mybtree{#1+#3}{#2+#4}{#3}{#4}{\bt@ndepth}
}
}{% else:
%% Do nothing
}
}
\newcommand*{\btree}[1]{\mybtree{0}{1}{1}{0}{#1}}
\makeatother

\begin{document}
%% Now we can draw our tree
\begin{tikzpicture}
\draw \btree{3};
\end{tikzpicture}

\end{document}


It should give something like this

So any help is welcome.

Can I offer you a forest?

## Code

\documentclass[tikz]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest}
Stern Brocot/.style n args={5}{%
content=$\frac{\number\numexpr#1+#3\relax}{\number\numexpr#2+#4\relax}$,
if={#5>0}{% true
append={[,Stern Brocot={#1}{#2}{#1+#3}{#2+#4}{#5-1}]},
append={[,Stern Brocot={#1+#3}{#2+#4}{#3}{#4}{#5-1}]}
}{}}% false (empty)
[,Stern Brocot={0}{1}{1}{0}{3}]
\end{forest}
\end{document}


## Code (with more stuff)

\documentclass[tikz]{standalone}
\usepackage{forest}
\makeatletter
\pgfmathdeclarefunction{strrepeat}{2}{%
\begingroup\pgfmathint{#2}\pgfmath@count\pgfmathresult
\let\pgfmathresult\pgfutil@empty
\pgfutil@loop\ifnum\pgfmath@count>0\relax
\expandafter\def\expandafter\pgfmathresult\expandafter{\pgfmathresult#1}%
\pgfutil@repeat\pgfmath@smuggleone\pgfmathresult\endgroup}
\makeatother
\tikzset{
Stern Brocot at/.style={at/.wrap 2 pgfmath args={([rotate around=180:(!##1)] !##22)}
{strrepeat("#1",\SBLevel)}{strrepeat("#1",\SBLevel-1)}},
Stern Brocot at*/.style n args={3}{
at/.wrap pgfmath arg={(!##1-|SB@#3)}{strrepeat("#1",#2)},
/forest/if={#2<\SBLevel}{append after command=
(\tikzlastnode) edge[densely dotted] (SB@#3@\the\numexpr\SBLLoop+1\relax)}{}}}
\forestset{
Stern Brocot*/.style n args={2}{
content=$\frac{#1}{#2}$,
edge=densely dotted,
if={level()<\SBLevel}{append={[,Stern Brocot*={#1}{#2}]}}{}},
Stern Brocot/.style n args={5}{
/utils/exec=\edef\SBLevel{#5},@Stern Brocot={#1}{#2}{#3}{#4}},
@Stern Brocot/.style n args={4}{
/utils/exec=\edef\SBTop   {\number\numexpr#1+#3\relax}% eTeX instead of PGFmath
\edef\SBBottom{\number\numexpr#2+#4\relax},
content/.expanded=$\frac{\SBTop}{\SBBottom}$,
if/.expanded={level()<\SBLevel}{% true
append={[,@Stern Brocot={#1}{#2}{\SBTop}{\SBBottom}]},
append={[,Stern Brocot*={\SBTop}{\SBBottom}]},
append={[,@Stern Brocot={\SBTop}{\SBBottom}{#3}{#4}]}
}{}}}% false (empty)
\begin{document}
\begin{forest}[,Stern Brocot={0}{1}{1}{0}{3}]
\coordinate[Stern Brocot at=1] (SB@left) coordinate[Stern Brocot at=3] (SB@right);
\foreach \SBLLoop in {\SBLevel, ..., 0}
\path node[Stern Brocot at*={1}{\SBLLoop}{left}]  (SB@left@\SBLLoop)  {$\frac01$}
node[Stern Brocot at*={3}{\SBLLoop}{right}] (SB@right@\SBLLoop) {$\frac10$};
\end{forest}
\end{document}


## Output (with more stuff)

• Very compact, with new syntax to learn. Thanks ! – Layus Jun 23 '13 at 11:04
• Is it also possible to draw the "parents" like in this image: commons.wikimedia.org/wiki/File:SternBrocotTree.svg ? – Martin Thoma Sep 30 '13 at 13:58
• @moose See my update. It includes a new PGFmath function strrepeat (strcat is from forest) that is used to place the 0/1 and 1/0 fractions in dependence of the maximum level. Those nodes will be placed wrongly if the tree doesn’t grow upwards or downwards. – Qrrbrbirlbel Sep 30 '13 at 17:27
• @Qrrbrbirlbel You may be surprised by the fact that using \edef\fracTop{...} or \def\fracTop{...} is exactly the same, because \numexpr is unexpandable. You probably want \edef\fracTop{\number\numexpr#1+#3\relax\space} or you'll be calling \numexpr very deeply nested (one level added for each recursion step, so in the example they are three). The final \space is for terminating the <number> when used later (spaces after numbers are ignored inside \numexpr, because they follow a constant). – egreg Sep 30 '13 at 17:35
• @egreg Thanks for your comment. I had \edef\FracTop{\number…} in earlier version of my codes and changed the implementation for some reason which I cannot remember anymore. I have now changed both implementations in my answer. The \space doesn’t seem to matter, though? – Qrrbrbirlbel Sep 30 '13 at 17:49

Here's a Metapost version - mainly to show that recursion works properly in luamplib.

\documentclass[border=10mm]{standalone}
\usepackage{unicode-math}
\setmainfont{TeX Gyre Schola}
\usepackage{luamplib}
\mplibtextextlabel{enable}
\begin{document}
\begin{mplibcode}
path S; S = superellipse(9 right, 12 up, 9 left, 12 down,0.79);
def connect(expr a,b) =
draw a -- b cutbefore S shifted a cutafter S shifted b
enddef;
def putfrac(expr num, den, pos) =
draw (left--right) scaled 4 shifted pos;
label.top(decimal num,pos);
label.bot(decimal den,pos);
enddef;
vardef mediant(expr a,b,c,d, depth, L, R) =
save m,n, p; pair p;
p = ((L+R)/2,depth * v);
m = a+c; n = b+d;
if depth > 1:
connect(p, mediant(a,b,m,n,depth-1, L, xpart p)) withcolor .53 red;
connect(p, mediant(m,n,c,d,depth-1, xpart p, R)) withcolor .53 blue;
connect(p, p shifted (0,-v)) dashed withdots scaled 1/2;
connect((L, ypart p), (L,ypart p-v)) dashed withdots scaled 1/2;
if d=0:
connect((R, ypart p), (R,ypart p-v)) dashed withdots scaled 1/2;
fi
fi
if depth > 0:
putfrac(m,n,p);
putfrac(a,b,(L,ypart p));
if d=0:
putfrac(c,d,(R,ypart p));
fi
fi
p
enddef;
beginfig(1);
v = 1.618cm;
z0 = mediant(0,1,1,0, 5, 0,220mm);
endfig;
\end{mplibcode}
\end{document}


For the fun of it, here TeX used to compute the predecessors of any given rational. Notice that this is not an answer to the question.

I am updating the version from September 2013 for the following reasons:

1. one needs to load explicitely xinttools now,

2. the method went through computation of coefficients of continued fraction, decrease by one of the last one, re-construction of fraction, and iteration, hence very inefficient,

3. looking at the result I realized there was a bug in the implementation, the decreased by one last coefficient was not correctly braced, hence the whole thing was buggy if some continued fraction coefficient was at least 10 :-(((

The new implementation proceeds not with the coefficients of the continued fraction, but with the convergents. It computes them once and for all. They are among the ancestors of the given fraction, but we need to add more fractions to find all ancestors. The recipe is explained in the code comments. Convergents correspond to locations where one changes direction in moving up the tree.

\documentclass{article}
\usepackage{xintcfrac, xinttools}

\makeatletter
\newcommand*\defSBAncestors [1]{%
% we first compute all convergents of a positive fraction
% we need to reverse the order, then we will scan and
% add the needed intermediate fractions.
% \SBA@i will see p/q.p'/q'....... n/1.\relax
% The ending n/1 is 0/1 if original fraction was <1.
% We need to add intermediate (p-p')/(q-q'), (p-2p')/(q-2q'), ...
\def\SBAncestors{}%
\expandafter\SBA@i
\romannumeral0\xintlistwithsep.{\xintRevWithBraces{\xintFtoCv{#1}}}.\relax
}
\def\SBA@i #1/#2.{\if1\xintiiIsOne{#1}\xintdothis\SBA@D\fi
\if1\xintiiIsOne{#2}\xintdothis\SBA@N\fi
\xintorthat\SBA@ii #1/#2.}
\def\SBA@ii #1/#2.#3/#4.{%
\edef\SBAncestors{\SBAncestors{#1/#2}}%
\edef\SBA@P {\xintiiSub{#1}{#3}}%
\edef\SBA@Q {\xintiiSub{#2}{#4}}%
\if1\xintiiGtorEq {#3}{\SBA@P}\xintdothis\SBA@i\fi
\xintorthat{\SBA@ii \SBA@P/\SBA@Q.}#3/#4.}

% Treat the special situations N/1 or 1/D

\def\SBA@D 1/#1.#2\relax {\edef\SBAncestors{\SBAncestors
\xintApply{1/\@firstofone}{\xintSeq[-1]{#1}{1}}}}

\def\SBA@N #1/#2\relax {\edef\SBAncestors{\SBAncestors\xintSeq[-1]{#1}{1}}}
\makeatother

\newcommand*\STRUT{\rule[4pt]{0pt}{9pt}} % line spacing

% #1 must evaluate to a **positive** fraction. It will be reduced to smalles
% terms initially.
\newcommand*\ShowParents [1]{%
\defSBAncestors {#1}%
$\xintListWithSep{\to}{\xintApply{\STRUT\xintFrac}\SBAncestors}$%
}

\begin{document}

\ShowParents {5}

\ShowParents {1/5}

\ShowParents {23/16}

\ShowParents {355/113}

\ShowParents {137197119/2110810820}

\end{document}