1

I am trying to adapt information from Draw lines on top of tikz forest to visualise an in-order traversal of a binary tree.

I tried defining an in-order traversal, modelled after the \forest@node@@foreach definition in forest.sty, but clearly I am doing something wrong as the example below gives me a "missing number, treated as zero" error. I'm not at all sure what I'm doing wrong.

The intent is to do walk by doing left-children first, then the current node, then right-children (recursively); I'm fine with assuming that nodes have at most two children.

Any help is appreciated! Thanks,

Christophe

\documentclass{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta}

\makeatletter
\def\forest@node@@forself#1{%
  \ifnum\forest@cn=0
  \else
  \forest@forthis{#1}%
  \fi
}%
\def\forest@node@@foreachinorder#1#2#3{%
  % #1 = do what
  % #2 = @first/@last
  % #3 = @last/@first
  \ifnum\forestove{#2}=0
  \else\@escapeif{%
    \forest@forthis{%
      \edef\forest@cn{\forestove{#2}}%
      \forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
    }%
  }\fi
  \forest@forthis{#1}%
  \ifnum\forestove{#3}=0
  \else\@escapeif{%
    \forest@forthis{%
      \edef\forest@cn{\forestove{#3}}%
      \forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
    }%
  }\fi
}
\forestset{
  define long step={tree in-order}{}{\forest@node@@foreachinorder{\forest@nodewalk@makestep}{@first}{@last}}
}
\makeatother
\forestset{%
  declare keylist register={through},
  through={},
  circles tree/.style={%
    for tree={circle, draw, fill=white, align=center},
  },
  tracing tree/.style={%
    delay={%
      for #1={%
        if phantom={}{through+/.option=name},
      }
    },
    before drawing tree={%
      tikz+/.wrap pgfmath arg={%
        \foreach \i [count=\j, remember=\i as \k] in {##1} \ifnum\j>1 \draw [densely dashed, -Stealth] (\k.west) -- (\i.west)\fi;
      }{(through)}
    },
  }
}
\newcommand*\tracetree[1][tree]{%
  \begin{forest}
    circles tree,
    tracing tree=#1,
    [$a$
      [$b$
          [$d$
              [$h$]
              [,phantom]
          ]
          [$e$
              [$i$]
              [$j$]
          ]
      ]
      [$c$
          [$f$
              [,phantom]
              [$k$]
          ]
          [$g$]
      ]
    ]
  \end{forest}%
}

\begin{document}

\tracetree[tree]
\end{document}
  • Welcome! I doubt this is a good way to do it, since it relies on Forest internals. For example, you shouldn't be using \forestove etc. at all, but rather the wrappers provided. (Your code is liable to break on update. More liable to break, that is. ) There are better ways, but I don't know what an in-order traversal is, so it is hard to implement it. – cfr Oct 30 '17 at 4:51
  • @cfr I doubt it's a good way to do it either! Thanks for the interest. An in-order traversal assumes that the tree being traversed is a binary tree, and visits the left-children of the current node, followed by the current node, followed by the right-children of the current node. For the tree in tex.stackexchange.com/questions/332300/…, an in-order traversal would visit the nodes in the order h d b i e j a f k c g. – Christophe Rhodes Oct 31 '17 at 14:00
  • If there is an odd number of children (e.g. 1), is the child traversed before or after the parent? – cfr Nov 2 '17 at 23:25
  • @cfr I would be satisfied with a solution which assumed (or asserted) that each node had exactly 0 or 2 children, with the author of the tree being responsible for using phantom nodes to make that true if necessary. I don't think there's a natural generalisation of in-order traversal to non-binary trees. – Christophe Rhodes Nov 4 '17 at 9:09
1

I was nearly there! The major thing I was missing was that the define long step was attempting to define a style, which was different from how the other tree traversal methods (built-in to forest.sty) are defined.

Surrounding the define long step call with calls to turn the automatic style generation off makes it work for me. Working example below.

\documentclass{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta}

\makeatletter
\def\forest@node@@forself#1{%
  \ifnum\forest@cn=0
  \else
  \forest@forthis{#1}%
  \fi
}%
\def\forest@node@@foreachinorder#1#2#3{%
  % #1 = do what
  % #2 = @first/@last
  % #3 = @last/@first
  \ifnum\forestove{#2}=0
  \else\@escapeif{%
    \forest@forthis{%
      \edef\forest@cn{\forestove{#2}}%
      \forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
    }%
  }\fi
  \forest@forthis{#1}%
  \ifnum\forestove{#3}=0
  \else\@escapeif{%
    \forest@forthis{%
      \edef\forest@cn{\forestove{#3}}%
      \forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
    }%
  }\fi
}
\def\forest@node@foreachinorder#1{%
  \forest@node@@foreachinorder{#1}{@first}{@last}%
}
\let\forest@nodewalkstephandler@styletrueorfalse\forest@nodewalkstephandler@stylefalse
\forestset{
  define long step={tree in-order}{}{\forest@node@foreachinorder{\forest@nodewalk@makestep}}
}
\let\forest@nodewalkstephandler@styletrueorfalse\forest@nodewalkstephandler@styletrue
\makeatother
\forestset{%
  declare keylist register={through},
  through={},
  circles tree/.style={%
    for tree={circle, draw, fill=white, align=center},
  },
  tracing tree/.style={%
    delay={%
      for #1={%
        if phantom={}{through+/.option=name},
      }
    },
    before drawing tree={%
      tikz+/.wrap pgfmath arg={%
        \foreach \i [count=\j, remember=\i as \k] in {##1} \ifnum\j>1 \draw [densely dashed, -Stealth] (\k.west) -- (\i.west)\fi;
      }{(through)}
    },
  }
}
\newcommand*\tracetree[1][tree]{%
  \begin{forest}
    circles tree,
    tracing tree=#1,
    [$a$
      [$b$
          [$d$
              [$h$]
              [,phantom]
          ]
          [$e$
              [$i$]
              [$j$]
          ]
      ]
      [$c$
          [$f$
              [,phantom]
              [$k$]
          ]
          [$g$]
      ]
    ]
  \end{forest}%
}

\begin{document}

\tracetree[tree in-order]
\end{document}

resulting tree

1

It really is not recommended to use code which relies on Forest internals. For example, \forestove ought not be used. In some cases, packages provide no alternative. However, Forest does provide wrappers for many of these macros and these are better choices. In particular, your code is less likely to break when Forest is updated.

That said, I think it should be possible to use mostly higher-level functionality to do this using node walks etc. I'm not confident that I've got a working algorithm in the code below. If I understood your code, I would try to use yours, but I don't.

And I know I've not got an elegant or especially parsimonious one.

However, I have (finally!) got one which may be enough to convey the general idea.

I'm not very good at figuring out walks through trees.

The basic idea is to define some new registers and options using the standard Forest syntax.

  declare boolean={two kids}{0},
  declare count={ordered}{-1},
  declare count register={ordering},
  declare toks register={order list},
  order list={},
  ordering'=0,

order list is similar to your through. two kids is used to mark nodes with two children, whose second child is not a phantom. ordered is an integer used for ordering purposes. (All you need really is a boolean, but I did it this way so the counting can be used to label the nodes, mostly for debugging purposes.) ordering is an integer used in the processing.

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\forestset{
  declare boolean={two kids}{0},
  declare count={ordered}{-1},
  declare count register={ordering},
  declare toks register={order list},
  order list={},
  ordering'=0,
  define long step={in order walk}{}{
    c,
    if n children=0{tempcountb'=1}{tempcountb/.min={>O{ordered}}{descendants}},
    until={> R_< {tempcountb}{0} }{
      u,
      tempcountb/.min={>O{ordered}}{descendants}
    }
  },
  in order/.style={
    for tree={
      circle, draw, minimum size=5ex, align=center, inner sep=0pt, anchor=mid, math content
    },
    delay={
      where={> On>{n children}{1} }{
        if={> On= {!2.phantom}{1} }{}{two kids}
      }{},
      where phantom={ordered=100}{},
    },
    before typesetting nodes={
      ordering'=0,
      where n children=0{
        if n=1{
          for in order walk={
            order me,
          }
        }{
          for nodewalk={reverse=in order walk}{order me},
          tempcounta'=0,
          for nodewalk={
            until={> R_< O_= | {tempcounta}{0} {level}{0} }{
              u,
              if nodewalk valid={2}{
                tempcounta/.min={>{O}{ordered}}{2,tree}
              }{}
            }
          }{order me},
        },
      }{}
    },
    order me/.style={
      if={>O_<O_=&{ordered}{0}{phantom}{0}}{
        ordering'+=1,
        label/.register=ordering,
        ordered/.register=ordering,
        if={> R+tt= {order list}{} }{}{order list+={,}},
        order list+/.option=name,
      }{},
    },
    /tikz/every label/.style={red, font=\footnotesize},
    tikz+={
      \edef\tempa{\foresteregister{order list}}
      \foreach \i [count=\j, remember=\i as \l] in \tempa \ifnum\j=1\else \draw [gray, densely dashed, ->] (\l.west) -- (\i.west)\fi;
    },
  },
}
\begin{document}
\begin{forest}
  in order
  [a
    [b
        [d
            [h]
            [,phantom]
        ]
        [e
            [i]
            [j]
        ]
    ]
    [c
        [f
            [,phantom]
            [k]
        ]
        [g]
    ]
  ]
\end{forest}

\end{document}

As I say, the algorithm is not at all neat, but the code should at least demonstrate a less dangerous approach to solving the problem.

walk through tree

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.