title: Algorithm to Render a Horizontal Binary-ish Tree in Text/ASCII form
body: <p>It's a pretty normal binary tree, except for the fact that one of the nodes may be empty.</p>
  
  <p>I'd like to find a way to output it in a horizontal way (that is, the root node is on the left and expands to the right).</p>
  
  <p>I've had some experience expanding trees vertically (root node at the top, expanding downwards), but I'm not sure where to start, in this case.</p>
  
  <p>Preferably, it would follow these couple of rules:</p>
  
  <ul>
  <li>If a node has only one child, it can be skipped as redundant (an "end node", with no children, is always displayed)</li>
  <li>All nodes of the same depth must be aligned vertically; all nodes must be to the right of all less-deep nodes and to the left of all deeper nodes.</li>
  <li>Nodes have a string representation which includes their depth.</li>
  <li>Each "end node" has its own unique line; that is, the number of lines is the number of end nodes in the tree, and when an end node is on a line, there may be nothing else on that line after that end node.</li>
  <li>As a consequence of the last rule, the root node might be better off in either the top left or the bottom left corner; top left is preferred.</li>
  </ul>
  
  <p>For example, this is a valid tree, with six end nodes (node is represented by a name, and its depth): <strong>EDIT: Please see bottom of question for an alternative, easier rendering</strong></p>
  
  <pre>        
  [a0]-----------[b3]------[c5]------[d8]
      \              \         \----------[e9]
       \              \----[f5]
        \-[g1]--------[h4]------[i6]
              \           \--------------------[j10]
               \-[k3]
  </pre>
  
  <p>Which represents the vertical, explicit binary tree:</p>
  
  <pre>
  0              a
                / \
  1            g   *
              / \   \
  2          *   *   *
            /     \   \
  3        k       *   b
                  /   / \
  4              h   *   *
                / \   \   \
  5            *   *   f   c
              /     \     / \
  6          *       i   *   *
            /           /     \
  7        *           *       *
          /           /         \
  8      *           *           d
        /           /
  9    *           e
      /
  10 j
  </pre>
  
  <p>(branches folded for compactness; <code>*</code> representing redundant, one-child nodes; note that <code>*</code>'s are <em>actual</em> nodes, storing one child each, just with names omitted here for presentation sake)</p>
  
  <p>(also, to clarify, I'd like to generate the first, horizontal tree; not this vertical tree)</p>
  
  <p>I say language-agnostic because I'm just looking for an algorithm; I say ruby because I'm eventually going to have to implement it in ruby anyway.</p>
  
  <p>Assume that each <code>Node</code> data structure stores only its id, a left node, and a right node.</p>
  
  <p>A master <code>Tree</code> class keeps tracks of all nodes and has adequate algorithms to find:</p>
  
  <ul>
  <li>A node's nth ancestor</li>
  <li>A node's nth descendant</li>
  <li>All end-node descendants of a node, and their count</li>
  <li>The generation of a node</li>
  <li>The lowest common ancestor of two given nodes</li>
  </ul>
  
  <p>I <em>already know</em>:</p>
  
  <ul>
  <li>The number of end nodes</li>
  </ul>
  
  <p>Anyone have any ideas of where I could start?  Should I go for the recursive approach?  Iterative?
  Some Psuedo-code would be pretty cool too, and much appreciated =)</p>
  
  <hr>
  
  <p><strong>progress</strong></p>
  
  <p>As per walkytalky's suggestion, I decided to see what it would look like to map each "relevant" or significant node to a grid, with the columns being the depth and the rows identifiable by their end nodes.  Here is what happens (skipping column 7 because there are no significant nodes in depth 7):</p>
  
  <pre>
  depth: 0  1  2  3  4  5  6  8  9  10
         a        b     c     d
                                 e
                        f
            g        h     i
                                    j
                  k
  </pre>
  
  <p>It should be easy enough to generate this grid, with either breadth-first or depth-first searches.  Perhaps most trivially by simply keeping a 2D array and placing every significant node found into it, inserting a row for every "second child".</p>
  
  <p>Now, knowing these facts:</p>
  
  <ul>
  <li>The last node in a row must be an end node</li>
  <li>Children are always to the right, and on the same row or lower, of their parent node.</li>
  <li>All non-end nodes must have exactly <strong>two</strong> children</li>
  <li>Therefore, all non-end nodes have children that are <strong>the first to the right of their column</strong>, the first child being on the same row, the second child being <em>n</em> rows below them, where <em>n</em> is the number of nodes on the right side of it.</li>
  </ul>
  
  <p>We can see that, given any valid grid, there is <strong>one unambiguous way</strong> to "connect the dots", so to speak; there is one unambiguous tree being represented.</p>
  
  <p>Now, the "connecting the dots" is no longer a binary-tree-structure question...it's simply a decoration question.  We just need to build an algorithm to properly place the right <code>-</code>'s and <code>\</code>'s where they can go, perhaps following only <em>simple grid/lexicographical rules</em>, instead of binary-tree-structure rules.</p>
  
  <p>Basically, this means that the problem of rendering a tree is now the much simpler problem of <strong>rendering a grid</strong>, with fancy decorations.</p>
  
  <p>Can anyone suggest any way of formulating these rules?  Or maybe a completely different method altogether?</p>
  
  <hr>
  
  <p><strong>edit</strong></p>
  
  <p>I have conceived of a much, much easier final rendering:</p>
  
  <pre>
  --d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)
  
   [a0 ]-------[b3 ]-------[c5 ]-------[d8 ]
     |           |           \---------------[e9 ]
     |           \---------[f5 ]
     \---[g1 ]-------[h4 ]-------[i6 ]
           |           \---------------------------[j10]
           \---[k3 ]
  
  --d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)
  </pre>
  
  <p>It might be easier to try to create this one, instead of the one I had posted earlier.  For one, it preserves a pretty grid shape, and you don't have to fickle with diagonal lines.  The rows are all mapped along clearly visible column lines.  Unfortunately, it is nowhere near as pretty as the first.</p>