Creating dots/lines brackets in tree with Tikz

Question

I am asking myself if I can create dots like the ones in the picture with tikz:

Code

\begin{tikzpicture}

\tikzstyle{level 1}=[sibling distance=60mm]
\tikzstyle{level 2}=[sibling distance=33mm]
\tikzstyle{level 3}=[sibling distance=10mm]
\tikzstyle{level 4}=[sibling distance=5mm]
\node {n} 
    child {node {$\frac{n}{3}$}
        child {node {$\frac{n}{9}$}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}}
        child {node {$\frac{n}{9}$}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}}}
        child {node {$\frac{n}{3}$}
        child {node {$\frac{n}{9}$}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}}
        child {node {$\frac{n}{9}$}
                        child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}}}
        child {node {$\frac{n}{3}$}
            child{node{$\frac{n}{9}$}
                            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}}
            child{node{$\frac{n}{9}$}
                            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}
            child{node {$\frac{n}{27}$}}}
    };

And I want to start the dot lines at last child nodes and between the child nodes.

Answer 1

Here is a solution using Tikz. The code was heavily based on this example of a recursion tree, but also heavily modified to fit your example image. Not sure if you wanted the cn/n to be actual fractions, but that's easily fixable starting from the code below.

Output

Code

\documentclass[margin=10pt]{standalone} 
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{trees,calc,arrows.meta,positioning,decorations.pathreplacing,bending}

\tikzset{
    edge from parent/.style={draw, thick, blue!70!black},
    no edge from this parent/.style={
        every child/.append style={
        edge from parent/.style={draw=none}}},
    level 3/.style={yshift=5cm},
    level 4/.style={level distance=5mm} 
         }

\begin{document}

\begin{tikzpicture}[
    level/.style={sibling distance=40mm/#1},
    text=blue!70!black,
    >=latex,
    font=\sffamily
    ]

\node (z){cn} 
  child {node (a) {cn/2}
    child {node  (b) {cn/4}
      child {node (b1) {$\vdots$}[no edge from this parent]
       child {node (b11) {c}}
      }
      child {node (b2) {$\vdots$}[no edge from this parent]
       child {node (b12) {c}}
      }
    }
    child {node (g) {cn/4}
      child {node (g1) {$\vdots$}[no edge from this parent]
       child {node (g11) {c}}
      }
      child {node (g2) {$\vdots$}[no edge from this parent]
       child {node (g12) {c}}
      }
    }
  }
    child {node (d) {cn/2}
      child {node  (e) {cn/4}
        child {node (e1) {$\vdots$}[no edge from this parent]
         child {node (e11) {c}}
        }
        child {node (e2) {$\vdots$}[no edge from this parent]
         child {node (e12) {c}}
        }
      }
      child {node (f) {cn/4}
        child {node (f1) {$\vdots$}[no edge from this parent]
         child {node (f11) {c}}
        }
        child {node (f2) {$\vdots$}[no edge from this parent]
         child {node (f12) {c}
         }
         }
  }
};

\node[left=5 of z]  (ln1) {cn}[no edge from this parent]
    child {node (ln2) {cn}[no edge from this parent]
        child {node (ln3) {cn}[no edge from this parent]
            child {node (ln4) {}[no edge from this parent]
                child {node (ln5) {cn}}}}};

\path (b12.north east) -- (g11.north west) node [midway] {$\cdots$};
\path (e12.north east) -- (f11.north west) node [midway] {$\cdots$};

\coordinate (cd1) at ($(f12)+(1,0)$);
\coordinate (nb1) at ($(g12)!.5!(e11)$);

\draw[blue!70!black,thick,<->,] 
    (cd1) -- (cd1|-z.east) node [near start, fill=white] {log(n)};

\draw[blue!70!black,dashed,thick,->]    
    ($(z.west)+(-1em,0)$) -- (ln1);
\draw[blue!70!black,dashed,thick,->]    
    ($(a.west)+(-1em,0)$) -- (ln2.east);
\draw[blue!70!black,dashed,thick,->]    
    ($(b.west)+(-1em,0)$) -- (ln3);
\draw[blue!70!black,dashed,thick,->]    
    ($(b11.west)+(-1em,0)$) -- (ln5);

\draw[blue!70!black,thick,decorate,decoration={brace,amplitude=10pt,mirror},->,-{latex[flex=1pt]}] (b11.south west) -- (f12.south east);
\end{tikzpicture}
\end{document}

Answer 2

Here's a solution using forest. Note that this takes the 'like this' of the target image extremely seriously. This means that the actual specification of the main tree is very, very compact:

   [c, name=node 1
     [, name=node 2 [, name=node 3 [][]][[][]]][[[][]][[][]]]
   ]

Obviously if you want something rather less generic, you can specify the contents of the nodes by hand.

Note also that there is really no reason for me to specify the labels of nodes 4-13 in the way I do. In particular, the specification of nodes numbered 10-13 is really just because I wanted to experiment a bit with node walks.

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest,textcomp}
\usetikzlibrary{positioning,arrows.meta,decorations.pathreplacing}
\begin{document}
 \begin{forest}
   for tree={
     font=\sffamily,
     before typesetting nodes={
       if={level>0}{
         if n children=0{
           append/.wrap pgfmath arg={
             [#1, font=\sffamily, edge=dotted]
           }{content("!r")},
           content={},
         }{
           content/.wrap 2 pgfmath args={#2n\textfractionsolidus#1}{int(level()*2)}{content("!r")}
         }
       }{
         delay n=1{
           content/.wrap value={##1n},
           node walk={
             every step/.style={alias=node 4}, F,
             every step/.style={alias=node 10}, N,
             every step/.style={alias=node 11}, N,
             every step/.style={alias=node 9},
             node walk={
               rL,
               node walk={
                 every step/.style={alias=node 12}, P,
                 every step/.style={alias=node 13}, P}
             }
           }
         }
       }
     },
   }
   [c, name=node 1
     [, name=node 2 [, name=node 3 [][]][[][]]][[[][]][[][]]]
   ]
   \begin{scope}[font=\sffamily, >=Triangle]
     \node (node 5) [left=25pt of node 4] {cn};
     \foreach \i/\j in {6/3,7/2,8/1} \node (node \i) at (node 5 |- node \j) {cn};
     \foreach \i/\j in {1/8,2/7,3/6,4/5} \draw [densely dashed, ->] (node \i.west) -- (node \j.east);
     \path [draw, decorate, decoration={brace, amplitude=10pt}] (node 9.south east) -- (node 4.south west);
     \path [draw, <->] (node 9.south east) +(15pt,0) coordinate (c) -- (c |- node 1.north) node [pos=.4, fill=white] {log(n)};
   \end{scope}
   \draw [dotted] (node 10.north east) -- (node 11.north west) (node 13.north east) -- (node 12.north west);
  \end{forest}
\end{document}