how to rearrange Forest tree?

Question

i need to arrange the above Forest tree in a configuration similar to this sketch diagram.

how am i able to arrange the nodes such that the '0' edge points directly south and the '1' edge is at a right angle to it and points directly east?

i need this is to be the same for all of the nodes which have all '0' prefixes (i.e. 0,00,000,0000)

any help would be great, i'm completely stumped.

additionally i need to add in the dividing horizontal lines and the annotations on the right hand side, i guess with tikz.

% not sure about these colours!
\definecolor{c1}{HTML}{FF7F00}
\definecolor{c2}{HTML}{048BA8}
\definecolor{c3}{HTML}{16DB93}
\definecolor{c4}{HTML}{EFEA5A}
\definecolor{c5}{HTML}{F29E4C}
\definecolor{c6}{HTML}{256EFF}
\definecolor{c7}{HTML}{46237A}


\scalebox{1.35}{
\begin{forest}
rt/.style={draw=green,line width=1pt},
peer/.style={draw=blue!60,edge={blue!60,line width=0.7pt}},
peerleaf/.style={edge={blue!60,line width=0.7pt}},
self/.style={draw=blue,fill=blue,edge={blue,line width=1pt}},
selfpeer/.style={draw=blue,line width=1pt,edge={blue,line width=1pt}},
unused/.style={draw=blue!20,edge={blue!20,line width=0.7pt}},
[{},grow=east, rt,for tree={circle,draw, l sep=20pt}
  [{},grow=east,selfpeer,edge label={node[midway,left] {0}}
    [{},grow=east,selfpeer,edge label={node[midway,left] {0}}
      [{},grow=east,selfpeer,edge label={node[midway,left] {0}}
        [{},grow=east,self,edge label={node[midway,left] {0}}]
        [{},grow=east,draw=c3,fill=c3,peerleaf,edge label={node[midway,right] {1}}]
      ]
      [{},grow=east,peer,edge label={node[midway,right] {1}}
        [{},grow=east,draw=c4,fill=c5,peerleaf,edge label={node[midway,left] {0}}]
        [{},grow=east,draw=c4,fill=c4,peerleaf,edge label={node[midway,right] {1}}]
      ]
    ]
    [{},grow=east,peer,edge label={node[midway,right] {1}} 
      [{},grow=east,peer,edge label={node[midway,left] {0}}
        [{},grow=east,draw=c1,fill=c1,peerleaf,edge label={node[midway,left] {0}}]
        [{},grow=east,unused,edge label={node[midway,right] {1}}]
      ]
      [{},grow=east,peer,edge label={node[midway,right] {1}}
        [{},grow=east,unused,edge label={node[midway,left] {0}}]
        [{},grow=east,draw=c2,fill=c2,peerleaf,edge label={node[midway,right] {1}}]
      ]
    ] 
  ]
  [{},grow=east,grow=east,peer,edge label={node[midway,right] {1}}
    [{},grow=east,peer,edge label={node[midway,left] {0}}
      [{},grow=east,peer,edge label={node[midway,left] {0}}
        [{},grow=east,unused,edge label={node[midway,left] {0}}]
        [{},grow=east,draw=c6,fill=c6,peerleaf,edge label={node[midway,right] {1}}]
      ]
      [{},grow=east,peer,edge label={node[midway,right] {1}}
        [{},grow=east,unused,edge label={node[midway,left] {0}}]
        [{},grow=east,draw=c7,fill=c7,peerleaf,edge label={node[midway,right] {1}}]
      ]
    ]
    [{},grow=east,unused,edge label={node[midway,right] {1}} 
      [{},grow=east,unused,edge label={node[midway,left] {0}}
        [{},grow=east,unused,edge label={node[midway,left] {0}}]
        [{},grow=east,unused,edge label={node[midway,right] {1}}]
      ]
      [{},grow=east,unused,edge label={node[midway,right] {1}}
        [{},grow=east,unused,edge label={node[midway,left] {0}}]
        [{},grow=east,unused,edge label={node[midway,right] {1}}]
      ]
    ]
  ] 
]
\end{forest}
}

Answer 1

Thanks Sebastiano.

Using the istgame package:

\documentclass[border=1mm]{standalone}
\usepackage{istgame}

\begin{document}

\begin{istgame}[every node/.style={fill=white,circle,inner sep=0pt,minimum size=5pt}]
\draw (-1,-1.45) --(7.5,-1.45);
\draw (-1,-3.95) --(7.5,-3.95);
\draw (-1,-6.2) --(7.5,-6.2);
%
\setistSolidNodeStyle{10pt}
\setistgrowdirection'{east}
\setistOvalNodeStyle{.8cm}
\xtShowEndPoints[oval node]
%
\xtdistance{25mm}{30mm}
\istrooto(0)<180>{\tiny Root}
\istb<grow=0>[draw=blue]{1}[bl]{}[center]
\istb<grow=-90>[draw=red]{0}[b]{}[center]
 \endist
 %
\xtdistance{20mm}{20mm}
\istrooto(1)(0-1){}
\istb[draw=blue]{1}[bl]{}[center]
\istb{0}[al]{}[center] 
\endist
%
\xtdistance{20mm}{20mm}
\istrooto(2)(1-1){}
\istb{1}[bl]{}[center]
\istb[draw=blue]{0}[al]{}[center] 
\endist
%
 \xtdistance{25mm}{20mm}
\istrooto(3)(0-2)
\istb<grow=14>{1}[bl]{}[center]
\istb<grow=-14>{0}[al]{}[center] 
\istb<grow=-90>[draw=red]{0}[b]{}[center]
 \endist
 %
\xtdistance{20mm}{10mm}
 \istrooto(4)(3-3)
\istb<grow=0>[draw=none]{1}[bl]{}[center]
\istb<grow=-90>[draw=red]{0}[b]{}[center]
 \endist
 %
 \xtTimeLineH[draw=none](0){-8}{0}{root}[font=\small]
 \xtTimeLineH[draw=none](3){-8}{0}{level1}[font=\small]
 \xtTimeLineH[draw=none](4){-8}{0}{level2}[font=\small,yshift=1cm]
 \xtTimeLineH[draw=none](4){-8}{0}{level3}[font=\small,yshift=-1.2cm]
\end{istgame}

\end{document}

Output:

Answer 2

I propose another way to draw your first picture using istgame package that for some points of view is similar to forest package. Here there is a starting point and I think that very slowly you can draw your first image.

\documentclass[a4paper,12pt]{article}
\usepackage{xcolor}
\usepackage{istgame}
\usepackage{amssymb}
\begin{document}
\begin{istgame}\setistSolidNodeStyle[blue]{10pt}
\setistgrowdirection'{east}
\setistOvalNodeStyle{.5cm}
\xtShowEndPoints[oval node]
\istrooto(0){}+{10mm}..{5cm}+
\istb[draw=blue]{\textcolor{blue}{1}}[al]
\istb[draw=blue]{\textcolor{blue}{0}}[bl]
\endist
\xtdistance{20mm}{20mm}
\istrooto(1)(0-1){}
\istb[draw=blue]{\textcolor{blue}{1}}[al]{}[center]
\istb[draw=blue]{\textcolor{blue}{0}}[bl]{}[center] 
\endist
\xtdistance{20mm}{20mm}
\istrooto(2)(0-2){}
\istb[draw=blue]{\textcolor{blue}{1}}[al]{}[center]
\istb[draw=blue]{\textcolor{blue}{0}}[bl]{}[center] 
\xtdistance{20mm}{20mm}
\istrooto(3)(1-1){}
\istb[draw=blue]{\textcolor{blue}{1}}[al]{}[center]
\istb[draw=blue]{\textcolor{blue}{0}}[bl]{}[center] 
\endist
\end{istgame}
\end{document}

In this image you can see that the circle can be colored with a specific code.

Answer 3

Here's a forest solution. It is neither general nor optimal, but it works. See the comments in the code.

\documentclass{standalone}
\usepackage{forest}
\forestset{
  % The idea is to first generate the tree and then rearrange the nodes.  We
  % need to then set various options for the nodes.  For some it makes sense to
  % set them as soon as the tree is generated, for others it is better to wait
  % until after rearrangement. These two keylists make this process
  % conceptually clean.  (The other option would be to use "delay", but
  % prepending is intertwined with delay cycles, so if we just used "delay", we
  % would need to compute how much delay is needed.)
  declare keylist={after generating tree}{},
  declare keylist={after reordering tree}{},
  typeset nodes stage/.style={
    process keylist=after generating tree,
    process keylist=after reordering tree,
    for root'=typeset nodes,
  },
  generate binary tree/.style={% #1 = number of levels
    if={#1>0}{
      append={[,generate binary tree/.process=n{#1-1}]},
      append={[,generate binary tree/.process=n{#1-1}]},
    }{}
  },
  pull left branches to the root/.style={
    % create an invisible root node first
    replace by={[,append,phantom]},
    % after the new root is created, iteratively prepend the first children to it
    delay={
      if n children={0}{}{for 1=pull left branch to the root},
    },
  },
  pull left branch to the root/.style={
    % a temporary name of the node to be pulled to the root
    alias=pull@temp,
    % pull
    for root={prepend={pull@temp}},
    % iterate
    if n children={0}{}{for 1=pull left branch to the root},
  },
  % Computes minimal and maximal x --- this is used both for drawing both the
  % horizontal lines and the level labels.  It must be executed on the phantom
  % root after x and y of all nodes were already computed.
  setup x for horizontal dividing line/.style={
    % {>...} below are argument processor expressions (manual 3.13) equivalent
    % to pgfmath "x() + min_x()" and "x() + max_x()".  ".min" and ".max" are
    % aggregate functions (3.14); here we set them loose on descendants (of the root)
    tempdimc/.min={>O2w2+d{x}{min x}{##1+##2}}{descendants},
    tempdimd/.max={>O2w2+d{x}{max x}{##1+##2}}{descendants},
  },
  horizontal dividing line/.style={
    % "y() + max_y()" for the tree of one of 00...00 nodes
    tempdima/.max={>O2w2+d{y}{max y}{##1+##2}}{tree},
    % "y() + min_y()" for the tree of the upper 00...00 node
    for next={tempdimb/.min={>O2w2+d{y}{min y}{##1+##2}}{tree}},
    % find the middle of these
    tempdima+/.register=tempdimb,
    tempdima:=2,
    % and draw the line: \draw (tempdimc,tempdima) -- (tempdimd,tempdima);
    % tempdimc and tempdimd were set by "setup x ..."
    tikz+/.process=R3w3{tempdima}{tempdimc}{tempdimd}{\draw (##2,##1) -- (##3,##1);},
  },
  level label/.style={
    % put the level label at (tempdimd,y)
    % tempdimd was set by "setup x ..."; y is the y position of the node (an option)
    tikz+/.process=ROw2{tempdimd}{y}{\node[anchor=west,font=\tiny] at (##1,##2) {#1};},
  },
}


\begin{document}
\begin{forest}
  generate binary tree=3,
  after generating tree={
    for tree={
      circle, draw,
      % Redefine the edge to the parent so that it is labelled. The label is
      % computed automatically; n = the child number (1 or 2), by compute
      % "n()-1" using the argument processor.
      edge path'/.process=Ow1+nw1{n}{#1-1}{
        (.child anchor) --
        node[fill=white,font=\noexpand\tiny,inner sep=1pt]{#1}
        (!u.parent anchor);
      },
    },
    pull left branches to the root,
    after reordering tree={
      % By using "for root'", we can set options for the phantom root created
      % when reordering the tree.
      for root'={
        % everything, including the phantom root, grows to the east
        for tree={grow=east},
        % widen the vertical gap between the leftmost nodes a bit
        s sep*=2,
        % Cleanly separate the subtrees of the leftmost nodes.
        for children={fit=band},
        % This stuff can only be done once x and y coordinates are known:
        before drawing tree={
          setup x for horizontal dividing line,
          % we walk through the leftmost nodes, top-down 
          for last={
            % the very top gets a special label, and no horizontal divide
            level label=root,
            for preceding siblings={
              % automatically figure out the level: "n'" is the child number,
              % counting from the last child
              level label/.process=Ow+nw{n'}{#1-1}{level #1},
              horizontal dividing line,
              % the vertical lines and zeros between the leftmost nodes
              % we'll use the "x" coordinate of the node, and "tempdima" is the
              % register holding "y" of the horizontal divide line we had just
              % drawn.
              tikz+/.process=ORw2{x}{tempdima}{
                % line from this node to the upper one (n=next)
                \draw[red] () -- (!n);
                % at (x,tempdima)
                \node[font=\tiny,fill=white,inner sep=1pt] at (#1,#2) {0};
              },
            }
          }
        }
      },
    },
  },
  % This is the starting tree :-)
  []
\end{forest}\hspace{2em}

\end{document}