Drawing (upward facing, potentially unlabelled) binary trees and forests in LaTeX

diagramsforeststacking-symbolstrees

I'm trying to figure out how to draw (forests of) potentially undecorated binary trees in Latex. So far, I've looked at the "forest" package, which I couldn't get to work with what I want. I'm hoping to draw binary trees that look like the following:

I'd also like to be able to draw forests of binary trees:

And finally, I'd like to be able to compose a forest of n trees with a tree of n leaves by vertical concatenation:

I appreciate that the last option might not exist as a built-in thing into a package, but figure I'd ask just in case.

Thanks!

Edit: Just in case anyone comes across this in the future — the accepted solution works without error for me after updating my MacTex distribution and then compiling with XeLaTeX.

Best Answer

Here is a macro \bintree that takes a tree as an argument using the syntax of the forest package.

is produced by the code:

\[
t=\bintree{[[[[][]][]]]} \hspace{2cm} 
f=\bintree{[[[[]]]]}\qquad\bintree{[[[[][]]]]}\qquad\bintree{[[[][[][]]]]}
\]

The macro uses a style defined in a \forestset. Here is the code:

\documentclass{article}

\usepackage{forest}

\forestset{bintree/.style={for tree={calign=fixed edge angles, grow'=north, edge=very thick, if n children=0{tier=x}{}},
     delay={where content={}{shape=coordinate, for current and siblings={anchor=north}}{}}}}

\newcommand{\bintree}[1]{\vcenter{\hbox{\scalebox{.5}{\tiny\begin{forest}bintree #1 \end{forest}}}}}

\begin{document}

\[
t=\bintree{[[[[][]][]]]} \hspace{2cm} 
f=\bintree{[[[[]]]]}\qquad\bintree{[[[[][]]]]}\qquad\bintree{[[[][[][]]]]}
\]

\end{document}

The composition is not automated, but can be accomplished by copying and pasting the trees into the leaves. Here is the code for t above:

\bintree{[[[[<paste tree here>][<paste tree here>]][<paste tree here>]]]}

And with the components of f pasted in:

The composition $f\circ t=\bintree{[[[[[[[[]]]]][[[[[][]]]]]][[[[][[][]]]]]]]}$

Related Solutions

[Tex/LaTex] Drawing binary trees with LaTeX labels

The most recent release of PGF has a number of graph drawing algorithms (requiring lualatex) including a version of the Reingold–Tilford method and can easily handle large numbers of nodes.

In the simplest case a tree can be specified like this:

\documentclass[tikz,border=5]{standalone}
\usetikzlibrary{graphs,graphdrawing,arrows.meta}
\usegdlibrary{trees}
\begin{document}
\begin{tikzpicture}[>=Stealth]
\graph[binary tree layout]{
  a -> {   
    b -> { 
      c -> { 
        d -> { e, f }, 
        g 
      }, 
    h -> { i, j }
    },
    k -> {
      l -> {
        m -> { n, o },
        p -> { q, r }
      }, 
      s -> {
        v -> {w, x},
        y -> {z}
      }
    }
  }
};
\end{tikzpicture}
\end{document}

enter image description here

It is also possible to create "graph macros" which mean the graph specification can be created more-or-less automatically, even using lua:

\documentclass[tikz,border=5]{standalone}
\usetikzlibrary{graphs,graphdrawing,graphs.standard,arrows.meta}
\usegdlibrary{trees}
\begin{document}
\tikzgraphsset{%
  levels/.store in=\tikzgraphlevel,
  levels=1,
  declare={full_binary_tree}{[
    /utils/exec={
      \edef\treenodes{%
\directlua{%
  function treenodes(l)
    if l == 0 then
      return "/"
    else
      return "/ [layer distance=" .. l*10 .. "]-- {" .. treenodes(l-1) .. ", " .. treenodes(l-1) .. "}"
    end
  end
  tex.print(treenodes(\tikzgraphlevel) .. ";")
}%
      }
    },
    parse/.expand once=\treenodes 
  ]}
}
\begin{tikzpicture}
\graph[binary tree layout, grow=down, sibling distance=5pt, significant sep=0pt, nodes={fill=red, draw=none, circle, inner sep=2.5pt, outer sep=0pt}]{
   full_binary_tree [levels=7];
};
\end{tikzpicture}
\end{document}

enter image description here

[Tex/LaTex] How to make binary search trees in an easy and straight forward way

i would simplify tree layout as follows:

and in drawing use package forest:

\documentclass[margin=3mm]{standalone}
\usepackage[edges]{forest}

\begin{document}
    \begin{forest}
for tree={
    grow=south,
    circle, draw, minimum size=3ex, inner sep=1pt,
    s sep=7mm
        }
[51
    [12
        [1]
        [43
            [36]
        ]
    ]
    [87
        [52
            [83]
        ]
    ]
]
\end{forest}
\end{document}

addedndum: considering caverac comment:

\documentclass[margin=3mm]{standalone}
\usepackage[edges]{forest}

\begin{document}
    \begin{forest}
for tree={
    grow=south,
    circle, draw, minimum size=3ex, inner sep=1pt,
    s sep=3mm
        }
[51
    [12
        [1]
        [43
            [36]
            [,no edge, draw=none]
        ]
    ]
    [87
        [52
            [,no edge, draw=none]
            [83] 
        ]
        [,no edge, draw=none]
    ]
]
\end{forest}
\end{document}

Best Answer

Related Solutions

[Tex/LaTex] Drawing binary trees with LaTeX labels

[Tex/LaTex] How to make binary search trees in an easy and straight forward way

Related Question