How can I align captions with each level of a tree drawn with tikz-qtree?

Question

I have drawn a binary tree using the TikZ-qtree package.

1) I now would like to align captions on the right of tree with each of its level---and I would like the placement to be automatic (ideally I only have to specify that I want it at Xpx from the right border of the tree, and the vertical positioning is taken care of by itself).

2) I would like to be able to draw several brackets in the tree ranging some of the (contiguous) nodes. Ideally, again, I would only specify the nodes, and not have to take care about positioning at all!!

Here is the code I have at the moment:

\documentclass{article}

\usepackage{tikz, pgf}
\usepackage{tikz-qtree}

\def\tn#1{{\bf #1}}    

\begin{document}
  \begin{tikzpicture}
    \Tree [.0 
            [.0 
              [.0
                [.{\tn 0} ]
                [.{\tn 1} ] ]
              [.1 
                [.{\tn 2} ]
                [.{\tn 3} ] ] ]
            [.1
              [.2 
                [.{\tn 4} ]
                [.0 
                  [.{\tn 0} ]
                  [.{\tn 1} ] ] ]
              [.3 
                [.1
                  [.{\tn 2} ]
                  [.{\tn 3} ] ]
                [.2
                  [.{\tn 4} ]
                  [.0 \edge[roof]; {... } ] ] ] ] ]
  \end{tikzpicture}
\end{document}

And here is an illustration of what I aim to do:

Any help much appreciated.

Answer 1

For the captions, you can draw a second tree to the right of the first tree with the branch style set to [draw=none]. This will ensure that the captions line up.

For underlining sets of nodes, you need to make the starting and ending nodes using the \node command, and then draw the underline. For this part, I've used some very useful code supplied by Jake, which implements in TikZ the equivalent of the PSTricks \ncbar command.

I've also removed your \tn macro, which is not needed, since you can define a separate style for each terminal (leaf) node in tikz-qtree.

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{tikz-qtree}
% The following code is due to Jake
% and implements in tikz the equivalent of PSTrick's \ncbar command
% http://chat.stackexchange.com/transcript/message/4527875#4527875
\tikzset{
    ncbar/.style={
        to path=(\tikztostart)
        -- ($(\tikztostart)!#1!90:(\tikztotarget)$)
        -- ($(\tikztotarget)!#1!-90:(\tikztostart)$)
        -- (\tikztotarget)
    },
    ncbar/.default=0.25cm
}
% end Jake's code 

\begin{document}
  \begin{tikzpicture}[every leaf node/.style={font=\bfseries}]
    \Tree [.0 
            [.0 
              [.0
                \node (0) {0}; 
                 1  ]
              [.1 
                2
                3 ] ]
            [.1
              [.2 
                \node (4) {4};
                [.0 
                  0
                  1 ] ]
              [.3 
                [.1
                  2
                  3 ]
                [.2
                  4
                  [.0 \edge[roof]; {... } ] ] ] ] ]
  \draw[ncbar=-.4cm] (0) to (4);
  \begin{scope}[xshift=2in]
  \tikzset{edge from parent/.append style={draw=none}, 
  every tree node/.append style={font=\sffamily\bfseries}
  }
  \Tree [[.{V=2} [.{V=4} [.{V=8} [.{V=5} ] ]]]]
  \end{scope}
  \end{tikzpicture}
\end{document}

Answer 2

Here's the same tree typeset with version 0.05 of the experimental justtrees.sty. (Should you wish to play guinea pig for me, please let me know so I can give you a current version. An earlier version is somewhere on this site.)

Answering this question using justtrees let me to fix one more bug....

---

To add the labels at the right you just say just=<label> for any of the nodes at the appropriate level of the tree. Since the labels have = in them, they need protection with curly brackets in this case.

The bracketing of the groups of nodes is done with a new style bracket me=<end node>. This should be applied to the leftmost node of the group. The argument should be a reference (name or forest relative name or alias etc.) to the rightmost node of the group. I've bracketed 2 such groups just for demonstration purposes here.

\documentclass[tikz,border=10pt]{standalone}
\usepackage{justtrees}% version 0.05
\begin{document}
\begin{justtree}
  {
    /tikz/every node/.append style={font=\sffamily},
    /tikz/select/.style={font=\sffamily\bfseries},
    just format={font=\sffamily\bfseries},
    /forest/bracket me/.style={
      tikz+={\draw [thick] (.south west) +(0,5pt) |- (#1.south east) -- +(0,5pt);}
    }
  }
  [0
    [0, just={v=2}
      [0, just={v=4}
        [0, just={v=8}, select, bracket me=4]
        [1, select]
      ]
      [1
        [2, select]
        [3, select]
      ]
    ]
    [1
      [2
        [4, select, name=4]
        [0
          [0, select, bracket me=p]
          [1, select]
        ]
      ]
      [3
        [1
          [2, just={v=5}, select]
          [3, select]
        ]
        [2
          [4, select, name=p]
          [0
            [\dots, triangle]
          ]
        ]
      ]
    ]
  ]
\end{justtree}
\end{document}

Answer 3

Another solution using forest:

  \begin{forest}
  label tree,
  for tree={
    circle,draw,
    s sep'=10pt, 
    edge+=thick,  
    font=\strut\footnotesize\sffamily,
  },
[A, name=lvl0
    [B
      [C, edge label={node[midway,left] {}} ] 
      [D] 
      [E
      [F]
      [G]
      ]
      ]
    [H, name=lvl1 
    [I
      [J]
      [K]
    ] 
      [L] 
      [M, name=lvl2 
      [N, name=lvl3
      ]
      ]
  ] 
]
\node[right=4.05cm of lvl0, Comment] {Level 0};
\node[right=1.75cm of lvl1, Comment] {Level 1};
\node[right=0.6cm of lvl2, Comment] {Level 2};
\node[right=0.6cm of lvl3, Comment] {Level 3};
\end{forest}

A minimal working code:

\documentclass[aspectratio=169,10pt]{beamer}
% \documentclass[border=10pt]{standalone}
\usepackage{tikz}
\usepackage{forest}
\forestset{%
  label tree/.style={
    for tree={tier/.option=level},
    level label/.style={
      before typesetting nodes={
        for nodewalk={current,tempcounta/.option=level,group={root,tree breadth-first},ancestors}{if={>OR={level}{tempcounta}}{before drawing tree={label me=##1}}{}},
      }
    },
    before drawing tree={
      tikz+={\coordinate (a) at (current bounding box.north);},
    },
  },
  label me/.style={tikz+={\node [anchor=base west] at (.parent |- a) {#1};}},
}

\usetikzlibrary{arrows.meta, calc, positioning}

\tikzset{%
    Comment/.style={%
        draw=none,
        inner sep=0mm,
        outer sep=0mm,
        minimum height=5mm,
        align=right
    },
}


\begin{document}
\begin{frame}{}
  \begin{forest}
  label tree,
  for tree={
    circle,draw,
    s sep'=10pt, 
    edge+=thick,  
    font=\strut\footnotesize\sffamily,
  },
[A, name=lvl0
    [B
      [C, edge label={node[midway,left] {}} ] 
      [D] 
      [E
      [F]
      [G]
      ]
      ]
    [H, name=lvl1 
    [I
      [J]
      [K]
    ] 
      [L] 
      [M, name=lvl2 
      [N, name=lvl3
      ]
      ]
  ] 
]
\node[right=4.05cm of lvl0, Comment] {Level 0};
\node[right=1.75cm of lvl1, Comment] {Level 1};
\node[right=0.6cm of lvl2, Comment] {Level 2};
\node[right=0.6cm of lvl3, Comment] {Level 3};
\end{forest}
\end{frame}
\end{document}

This code will work for both beamer as well as other classes.