How to draw search space tree in a dynamic manner

Question

I am visualising the search space for a set of binary variables. I have done it for three variables before; and now I am extending it to six but seems a tedious work to do. Thus, I am wondering if there is any systematic/dynamic way to draw the search tree. For example, I just supply the number of variables and a tree would be drawn with dummy names. is such a tool exist?

Here is my code for the three binary variables.

\begin{figure}[htp]
\begin{center}
\begin{tikzpicture}[scale=.8,level/.style={sibling distance=40mm/#1},node distance=1cm]
\node [circle,draw] (root){$$}
    child {node (a)at (0,.5){$1$}
        child {node  (ab){$2$}
        child {node (abc){$3$}}
        child {node (abc2){$4$}}
        }
        child {node  (ab2){$5$}
            child {node (ab2c) at(0.3,0){$6$}}
            child {node (ab2c2){$7$}}
        }
    }
      child {node (a2)at (0,.5){$8$}
      child {node  (a2b){$9$}
                          child {node at (.2,0) (a2bc){$10$}}
            child {node at(-.2,0) (a2bc2){$11$}}
            }
        child {node  (a2b2){$12$}
                    child {node  (a2b2c){$13$}}
            child {node (a2b2c2){$14$}}
        }
    };
\end{tikzpicture}
\end{center}
\caption{search space}
\label{search_space}
\end{figure}

which will draw this

Answer 1

This answer includes a forest implementation.

In a forest environment, we only need to add one root node with the ary Tree key. The three arguments are:

1. The value of the root (never shown, usually 0).
2. The number of children per node (in your example 2).
3. The highest level (in your example 3); note that the root node is in level 0.

The ary Tree style automatically adds #2 children (see repeat key) which all use the ary Tree option but with the value of their parent’s contant as first argument.

This is used in the content key to set the value of the node. The formula is:

<value of the parent node> + 1 + (<i> - 1) * <Sum>

Here, <i> is just an integer for the child (the first child is <i> = 1, the second has <i> = 2 and so on). The <sum> is the sum of children and children’s children for a node of the current level. This sum is calculated for every needed level at the root node with the ary Tree calc. (There also exists a \foreach-less solution that uses a basic TeX loop and counters and doesn’t any global macros.)

The aryTree function that is defined via the declare function key is used to access this summed value using the already evaluated value of level() in a \csname …\endcsname construction.

I have added the option calign=first in the last example which in my opinion shows the algorithm of the tree a little better. (Don’t ask me why one needs an additional delay for every extra level.)

Code

\documentclass[tikz]{standalone}
\usepackage{forest}
\tikzset{
  declare function={aryTree(\aryLevel)=\csname aryTree@level@\aryLevel\endcsname;}}
\forestset{
  ary Tree node/.style={node options={align=center}},
  setup ary Tree nodes/.style 2 args={
    ary Tree node/.append style={node options={text width={width("#1")},#2}}},
  ary Tree root/.style={node options={circle, draw, inner sep=+0pt, minimum size=+1em}},
  ary Tree calc/.code 2 args={%
    \expandafter\def\csname aryTree@level@\the\numexpr#2+1\relax\endcsname{0}%
    \foreach \aryLevel in {#2,...,1}{%
      \pgfmathparse
      {(#1)^(#2-\aryLevel)+\csname aryTree@level@\the\numexpr\aryLevel+1\relax\endcsname}%
      \global\expandafter\let\csname aryTree@level@\aryLevel\endcsname\pgfmathresult}},
  ary Tree/.style n args={3}{% #1 = parent value, #2 = children per node, #3 = level
    if={level()>0}{
      content/.pgfmath={int(#1 + 1 + (n() - 1) * aryTree(level()))},
      ary Tree node
    }{ary Tree calc={#2}{#3}},
    if/.expanded={level()<#3}{
      repeat={#2}{
        append={[,ary Tree={\forestove{content}}{#2}{#3}]}}}{}}}
\begin{document}
\begin{forest} setup ary Tree nodes={00}{}
[,ary Tree={0}{2}{3}, ary Tree root]
\end{forest}
\begin{forest} setup ary Tree nodes={00}{inner ysep=+2pt}, 
               ary Tree node/.append style={s sep=+0pt}
[,ary Tree={0}{3}{3}, ary Tree root]
\end{forest}
\begin{forest} setup ary Tree nodes={00}{inner ysep=+2pt},
               ary Tree node/.append style={s sep=+0pt},
               delay={for tree={calign=first}}
[,ary Tree={0}{4}{2}, ary Tree root]
\end{forest}
\end{document}

Output

ary Tree={0}{4}{4}