Algorithm to Render a Horizontal Binary-ish Tree in Text/ASCII form

If there are N end nodes, there must be N-1 internal nodes with 2 children. (There can be any number of internal nodes with 1 child, which we will have to count to get the depths but otherwise ignore.) Generating the tree is thus equivalent to positioning these nodes on a grid, where:

• the number of rows in the grid is N
• I think the number of columns is between 1+floor(log2(N)) and 2*N-1, depending on how much overlap there is; this probably doesn't matter much for our purposes, though
• each endpoint appears on a different row
• all nodes at the same depth appear in the same column
• all internal nodes appear on the same row as their rightmost descendant endpoint

So, let's see:

• Walk the tree depth-first, right-to-left.
• For each endpoint, record its depth and label.
• For each 2-child internal, record its depth, label and the indices of both rightmost and leftmost child endpoints.
• Sort the whole lot by depth -- this gives you the column ordering, with the number of distinct depths giving the actual number of columns. (All other ordering should come out automatically from the walk, I think, but that's not the case here because any branch can be any depth.)
• Place all the nodes in the grid.
• Mark empty cells to the right of each non-endpoint node as horizontal branches.

• Mark empty cells down from each internal node to the row above its left child as vertical branches, and the cell at the level of the left child as a junction.

• Print with appropriate ASCII decoration.

Update:

As you say, the positioning is enough to unambiguously determine the connections, but you still need to do some bottom-up work to get that right, so I'd probably still do the "mark" steps during the grid building.

I sort of thought t

Below is fully functional C# code that does exactly what you want. How it does it:

• The tree is represented as objects from classes that inherit from Node
• First compute the number of leaves and create an array of that much lines
• Then for each level:
  • find out on what lines are we going to write
  • for those lines, compute the maximum of what is already on those lines
  • write the all the nodes to column max(number from previous step, end of previous level)+1; prepend with - to get to that column
  • write diagonal lines from all binary nodes up to the line of their right child (in my program first child is left, second is right, you have it the other way around)
  • advance one level

The algorithm makes sure that each level starts only after previous ends. That is probably good choice for short names, but for longer names, this probably shouldn't be enforced.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SO_ASCII_tree
{
    class Program
    {
        static void Main()
        {
            Node root = …;

            StringBuilder[] lines = Enumerable.Range(0, root.Leaves).Select(i => new StringBuilder()).ToArray();

            Node[] currentLevel = new Node[] { root };
            int level = 0;
            int min = 0;
            int max = 0;
            while (currentLevel.Any())
            {
                NamedNode[] namedNodes = currentLevel.OfType<NamedNode>().ToArray();
                if (namedNodes.Any())
                {
                    min = namedNodes.Select(node => lines[node.Line].Length).Max();
                    min = Math.Max(min, max);
                    if (min != 0)
                        min++;
                    foreach (NamedNode namedNode in namedNodes)
                        WriteAtPosition(lines[namedNode.Line], namedNode.Write(lev