# Recursive method to build a tree with tikz

I would like to translate the next example of a Bernoulli tree built with pst-tree with tikz but I don't know if it's possible :

\documentclass{article}
\usepackage{pstricks,pst-tree}

\makeatletter

\newcount\@Bernoudepth
\newcount\@Bernoumaxdepth

\newcommand\Bernoutree[8][treemode=R,nodesep=1ex,levelsep=12ex]{%
% #2 = depth of tree
% #3 = name for success
% #4 = name for miss
% #5 = probability of a success
% #6 = position of  #5
% #7 = probability of a miss
% #8 = position of #7
\begingroup
% initialize  parameters
\psset{treemode=R,nodesep=1ex,levelsep=12ex}%
\psset{#1}%
\@Bernoumaxdepth #2\relax
\def\@Reussite{#3}%
\def\@Echec{#4}%
\def\@probareussite{#5}%
\def\@Argreussite{#6}%
% if no parameter of position
% center position
\ifx\empty\@Argreussite
\def\@Argreussite{0.5}%
\fi
\def\@probaechec{#7}%
\def\@Argechec{#8}
\ifx\empty\@Argechec
\def\@Argechec{0.5}%
\fi
% First call  (empty root, level 1)
\pstree{\TR{}}{\@Bernoutree{1}}
\endgroup
}
\newcommand\@Bernoutree[1]{%
% #1 = recursive depth
% initialize the depth
\@Bernoudepth #1\relax
\ifnum\@Bernoudepth=\@Bernoumaxdepth
% if depth  max is reached
% we place the two final nodes
\TR{\@Reussite}\taput[tpos=\@Argreussite]{\@probareussite}
\TR{\@Echec}\tbput[tpos=\@Argechec]{\@probaechec}
% it's finished
\else
% else we build with a recursive method
% the two branches of higher level
\pstree{\TR{\@Reussite}\taput[tpos=\@Argreussite]
{\@probareussite}}{\@Bernoutree{\the\@Bernoudepth}}
\pstree{\TR{\@Echec}\tbput[tpos=\@Argechec]
{\@probaechec}}{\@Bernoutree{\the\@Bernoudepth}}
\fi
}
\makeatother

\pagestyle{empty}

\begin{document}

\Bernoutree[levelsep=18ex,treenodesize=0pt]{4}{$R$}{$E$}{$p$}{}{$q$}{}

\end{document}


Actually I get the tree with the next method but it's not a recursive method.

\documentclass{scrartcl}
\usepackage{pgf,tikz}
\usetikzlibrary{trees,arrows}

\makeatletter
\newcount\tkz@Berndepth
\newdimen\tkz@BernLEN
\tkz@BernLEN=24em
\def\tkzBernTreeSet#{\pgfqkeys{/berntree}}

\pgfqkeys{/berntree}{%
success/.code      = \def\tkz@bern@success{#1},
miss/.code         = \def\tkz@bern@miss{#1},
p/.code            = \def\tkz@bern@pbsuccess{#1},
q/.code            = \def\tkz@bern@pbmiss{#1},
node success style/.style  = {inner sep=2pt,outer sep=3pt},
node miss style/.style     = {inner sep=2pt,outer sep=3pt},
edge style/.style  = {->,>=latex',shorten <= 6pt},
root style/.style  = {draw,circle},
success/.initial   = S,
miss/.initial      = E,
p/.initial         = $p$,
q/.initial         = $1-p$,
gap/.code          = \def\tkz@bern@gap{#1},
length/.code       = \def\tkz@bern@length{#1}
}

\def\tkz@brntree#1#2{%
\node[/berntree/root style] {};
\begin{scope}[level distance=\tkz@bern@length,
level 1/.style={sibling distance=#2}]
\node[] (root) at (#1) {}
[grow=right]
child[/berntree/edge style] {%
node[/berntree/node miss style](tkz@E\the\tkz@Berndepth) {\tkz@bern@miss}
edge from parent node[fill=white] {\tkz@bern@pbmiss}}
child [/berntree/edge style] {%
node[/berntree/node success style] (tkz@S\the\tkz@Berndepth) {\tkz@bern@success}
edge from parent node[fill=white] {\tkz@bern@pbsuccess}
};
\end{scope}}%

\def\tkzBernTree{\pgfutil@ifnextchar[{\tkz@BernTree}{\tkz@BernTree[]}}
\def\tkz@BernTree[#1]#2{%
\begingroup
\pgfqkeys{/berntree}{%
success = S,
miss= E,
node success style/.style  = {inner sep=2pt,outer sep=3pt,draw,minimum width=1.5em,minimum height=1.5em},
node miss style/.style  = {inner sep=2pt,outer sep=3pt,circle,draw,minimum width=1.5em},
p=$p$,
q=$q$,
gap=8cm,
length=3cm}
\pgfqkeys{/berntree}{#1}
\tkz@BernLEN=\tkz@bern@gap\relax
\tkz@Berndepth 0\relax
\node (tkz@S0) at (0,0){};
\def\tkz@bn@level{#2}
\ifcase\tkz@bn@level%
\or%
\tkz@brntree{tkz@S0}{\tkz@BernLEN}
\or%
\tkz@brntree{tkz@S0}{\tkz@BernLEN}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {1}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\or%
\tkz@brntree{tkz@S0}{\tkz@BernLEN}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {1}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {2,3}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\or%
\tkz@brntree{tkz@S0}{\tkz@BernLEN}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {1}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {2,3}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {4,5,6,7}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\or%
\tkz@brntree{tkz@S0}{\tkz@BernLEN}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {1}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {2,3}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {4,...,7}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\divide \tkz@BernLEN by 2 %
\foreach \nd in {8,...,15}{
\tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
\tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
\fi
\endgroup
}
\makeatother
\begin{document}

\begin{tikzpicture}[yscale=1.2]
\tkzBernTree[root style/.style  = {fill,circle,outer sep =1pt,inner sep=2pt}]{4}

\end{tikzpicture}

\end{document}

-
Maybe the code from tikz-qtree might be useful to look at. –  Alan Munn Dec 26 '11 at 15:55
Yes good idea... –  Alain Matthes Dec 26 '11 at 17:10

The following is a possible solution. I had to separate the node creation and the labelling of the edges. I've also been thinking of doing this with a lindenmayer system but that failed. Enjoy. (I minimised on style settings and focussed on the nub of the matter.)

The tree creation wasn't so straightforward and I had to fight hard to increment and decrement the TeX counter \depth. In the end I ended up doing this as part of a node style. It also required the placement of a dummy coordinate that incremented the level upon returning from the recursion.

The labelling exploits the fact that tikz labels the children of a parent with the labels (parent-1), (parent-2), ..., where (parent) is the label of the parent.

The rest is pretty much straightforward.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{calc}

\newcount\depth

\makeatletter
\newcommand*\bernoulliTree[1]{%
\depth=#1\relax
\draw node(root)[bernoulli/root] {}[grow=right] \draw@bernoulli@tree;
\draw \label@bernoulli@tree{root};
}

\def\draw@bernoulli@tree{%
\ifnum\depth>0
child foreach \type/\label in {left child/$S$,right child/$F$} {%
node[bernoulli/\type]{\label} \draw@bernoulli@tree
}
coordinate[bernoulli/increment] (dummy)
\fi%
}

\def\label@bernoulli@tree#1{%
\ifnum\depth>0
($(#1)!0.5!(#1-1)$) node[fill=white,bernoulli/decrement] {$p$}
\label@bernoulli@tree{#1-1}
($(#1)!0.5!(#1-2)$) node[fill=white] {$1-p$}
\label@bernoulli@tree{#1-2}
coordinate[bernoulli/increment] (dummy)
\fi%
}

\makeatother

\tikzset{bernoulli/.cd,
root/.style={circle,fill,black},
left child/.style={draw,bernoulli/decrement},
right child/.style={draw,circle}}

\begin{document}

\begin{tikzpicture}[level distance=2cm,
level 1/.style={sibling distance=4cm},
level 2/.style={sibling distance=2cm},
level 3/.style={sibling distance=1cm}]
\bernoulliTree{3}
\end{tikzpicture}

\end{document}


-
This looks very promising. I need to study attentively your code. At the first approach, perhaps it's possible to integrate the sibling distance automatically. –  Alain Matthes Dec 26 '11 at 13:02
Thanks. As I said, the most difficult was to adjust the counter. The tikz/pgf parser won't allow much when it's parsing a tree. It is possible to include the sibling distance automatically, but I wanted to keep the example simple. (It is also possible to do without the child foreach'' but I thought the current version is neater.) –  Marc van Dongen Dec 26 '11 at 13:09
Neat code; very elegant ! –  Alain Matthes Dec 27 '11 at 7:47