Old school tree display

Old school tree display

Rate This
  • Comments 51

I'm back from my various travels, refreshed and ready for more fabulous adventures in coding. A while back I did a coding challenge for you all: to turn a sequence of strings into a fancy comma-separated list. You might also recall that I did a bit on how to generate all possible arbitrary trees, which I notated with a simple bracing format. Today, let's combine those two problems.

What I want to do is create a function which takes an arbitrary tree where each node has some string data, and turns it into a fancy string that has some nice properties. It should be compact and easy to read; the structure of the tree should be apparent from the output string. I'd like to have one node per line, and each line ends with the data in the string (which we can think of as the name of the node.)

Here's my Node class:

class Node
{
    public Node(string text, params Node[] children)
    {
        this.Text = text;
        this.Children = children ?? new Node[] {};
    }
    public string Text { get; private set; }
    public IList<Node> Children { get; private set; }
}

Pretty straightforward. Note that there are no parent pointers.

My challenge to you is to fill in the blanks here:

sealed class Dumper
{
    static public string Dump(Node root) { /* ... */ }
    /* ... */
}

such that the Dump method produces this string:

a
├─b
│ ├─c
│ │ └─d
│ └─e
│   └─f
└─g
  ├─h
  │ └─i
  └─j

when given this tree:

var root = new Node("a",
    new Node("b",
        new Node("c",
            new Node("d")),
        new Node("e",
            new Node("f"))),
    new Node("g",    
        new Node("h",
            new Node("i")),
        new Node("j")));

Notice that I am using the Unicode "box drawing" characters │ ├ ─ └. I used to write code to build user interfaces like this back in my Commodore 64 programming days. Ah, the halcyon days of my youth.

I've posted my solution here, but NO CHEATING. Write your own solution first, and then see how yours compares to mine.

When I discussed how to build a graph colourizer / Sudoku solver in July I did some analysis of the design decisions I made along the way. What are your design criteria as you approach this problem? For example, are you going to automatically go for a recursive solution because tree problems are usually most easily solved with recursion? Or are you going for an iterative solution? Will you prioritize obvious correctness over cleverness or vice versa? Did you miss having parent pointers? And so on - I'd be interested to know what your design criteria and choices were.

And... go!

  • Here's my solution.  Main trade off is going for simplicity and readability (building from the deeper levels out and using string concatenation) instead of speed (using a StringBuilder and appending everything in order).

           public static string Dump(Node root)

           {

               return string.Join(Environment.NewLine, DumpSubTree(root).ToArray());

           }

           private static IEnumerable<string> DumpSubTree(Node node)

           {

               yield return node.Text;

               for (int i = 0; i < node.Children.Count; i++)

               {

                   bool last = i == node.Children.Count - 1;

                   bool first = true;

                   foreach (string line in DumpSubTree(node.Children[i]))

                   {

                       if (first && last)

                           yield return "└─" + line;

                       else if (first)

                           yield return "├─" + line;

                       else if (last)

                           yield return "  " + line;

                       else

                           yield return "│ " + line;

                       first = false;

                   }

               }

           }

  • Here's my attempt (it's been awhile since I've done any coding!)  I split the presentation logic as much as I could, but it probably could use a thorough code review.  I really am happy that "var" exists now, BTW: it gets rid of needless redundancies.

    -----

    using System;

    using System.Collections.Generic;

    using System.Text;

    public class TreeDump {

     public static void Main() {

       var root = new Node("a",

           new Node("b",

               new Node("c",

                   new Node("d")),

               new Node("e",

                   new Node("f"))),

           new Node("g",    

               new Node("h",

                   new Node("i")),

               new Node("j")));

        Console.WriteLine(StringNodeDump.ShowTree(root));

     }

    }

    public class Node {

     public Node(string text, params Node[] children) {

       this.Text = text;

       this.Children = children ?? new Node[] {};

     }

     public string Text { get; private set; }

     public IList<Node> Children { get; private set; }

    }

    public abstract class GenericNodeDump {

     public GenericNodeDump(Node root) {

       DumpNodes(root, new bool[] {});

     }

     private void DumpNodes(Node start, IList<bool> levels) {

       DisplayNode(start.Text, levels);

       /* Each element indicates whether that level contains more nodes */

       var newlevels = new List<bool>(levels);

       newlevels.Add(true);

       IEnumerator<Node> children = start.Children.GetEnumerator();

       if(children.MoveNext()) {

         Node current = children.Current;

         Node next;

         do {

           DisplaySpace(newlevels);

           if(children.MoveNext()) {

             next = children.Current;

           } else {

             /* Indicate that this level is finished */

             newlevels[newlevels.Count - 1] = false;

             next = null;

           }

           DumpNodes(current, newlevels);

           current = next;

         } while (next != null);

       }

     }

     protected abstract void DisplayNode(string text, IList<bool> levels);

     protected abstract void DisplaySpace(IList<bool> levels);

    }

    public sealed class StringNodeDump: GenericNodeDump {

     public StringNodeDump(Node root): base(root) { }

     private StringBuilder output = new StringBuilder();

     protected override void DisplayNode(string text, IList<bool> levels) {

       for(int i = 0; i < levels.Count - 1; ++i) {

         output.Append(levels[i] ? "│   " : "    ");

       }

       if(levels.Count > 0) {

         /* Display the appropriate branch indicator */

         output.Append(levels[levels.Count - 1] ? "├── " : "└── ");

       }

       output.Append(text);

       output.Append('\n');

     }

     protected override void DisplaySpace(IList<bool> levels) {

       for(int i = 0; i < levels.Count; ++i) {

         output.Append(levels[i] ? "│   " : "    ");

       }

       output.Append('\n');

     }

     public string GetResult() { return output.ToString(); }

     public static string ShowTree(Node root) {

       return new StringNodeDump(root).GetResult();

     }

    }

  • Here's my code. It turned out to be virtually equivalent to carlos's solution, but I'll post it anyway. Yes, I automatically went for recursion, since an iterative solution would have required an explicit stack in some form or another anyway. If I had gone for a clever iterative solution, parent pointers could have been useful, but not for recursion. At first, I was going to have my core recursive method return a list of strings, which would then have been prefixed appropriately one recursion level up, but then I realized it was much simpler just to pass in prefixes as parameters. Then, it was trivial to get the StringBuilder performance boost, so I went for that. I didn't think much about obvious correctness vs. cleverness, although I think this does fairly well in both ;).

    public static string Dump(Node node) {

    var sb = new StringBuilder();

    DumpCore(sb, "", "", node);

    return sb.ToString();

    }

    public static void DumpCore(StringBuilder sb, string firstLinePrefix, string remainingLinePrefix, Node node) {

    sb.AppendLine(firstLinePrefix + node.Text);

    for (int i = 0; i < node.Children.Count; i++) {

    if (i < node.Children.Count - 1) {

    DumpCore(sb, remainingLinePrefix + "├─", remainingLinePrefix + "│ ", node.Children[i]);

    } else {

    DumpCore(sb, remainingLinePrefix + "└─", remainingLinePrefix + "  ", node.Children[i]);

    }

    }

    }

    I think your solution is slightly better than mine, though, both in terms of simplicity and performance, since it has one less parameter (really two less, but it has an implicit "this" parameter used to pass the StringBuilder). However, I think mine is arguably slightly easier to understand.

  • I posted mine to "mcherm.com/.../eric-lippert-tree-challenge", along with the notes I kept on design choices and the process I followed. As a teaser, I'll mention:

     (1) I used a cool language feature not found in .Net (although a similar approach would work without special syntax support)

     (2) The best thing I learned had to do with figuring out how to discover the natural unit for recursion.

    Thanks, Eric, for an interesting challenge.

  • mcherm: I was curious what cool language feature you used in Python that wasn't available in C#, so I did a strict line-by-line translation.  Aside from having to know what type to use in one place (dumper_helper has to return IEnumerable) and having to declare variables (mostly dynamic to stay faithful to the original), the only feature that didn't directly translate was the array slice (translated to a loop iterating over array indices). While it's certainly a useful feature, it hardly seems worth mentioning. For reference, here's the main part of my faithful (non-idiomatic) C# 4 translation of your Python 3 code:

       static class __main__

       {

           class Node

           {

               public dynamic text, children;

               public Node(dynamic text, params dynamic[] children)

               {

                   this.text = text;

                   this.children = children;

               }

           }

           static dynamic NEWLINE = "\n";

           static dynamic dumper(dynamic root)

           {    // string.Join(x, y) == x.join(y)

               return string.Join("", dumper_helper(root, new dynamic[]{}));

           }

           static dynamic sequence_and_item(dynamic sequence, dynamic item)

           {    // Enumerable.Concat == itertools.chain

               return Enumerable.Concat(sequence, new[] { item });

           }

           static IEnumerable dumper_helper(dynamic node, dynamic prefix)

           {

               yield return node.text;

               yield return NEWLINE;

               var children = node.children;

               if (children.Length >= 1)

               {    // we have to emulate list slicing here by iterating over array indices

                   dynamic child;

                   for (var i = 0; i < children.Length - 1; i++)

                   {    // could have used foreach (child in children.Take(children.Length-1))

                       child = children[i];

                       foreach (var x in prefix)

                           yield return x;

                       yield return "├─";

                       foreach (var x in dumper_helper(child, sequence_and_item(prefix, "│ ")))

                           yield return x;

                   }

                   child = children[children.Length - 1];

                   foreach (var x in prefix)

                       yield return x;

                   yield return "└─";

                   foreach (var x in dumper_helper(child, sequence_and_item(prefix, "  ")))

                       yield return x;

               }

           }

       }

  • Design criteria: Short and simple, not overengineered. Can always change/rewrite if additional requirements pop up.

    Solution:

           static public string Dump(Node root)

           {

               var head = root.Text + "\n";

               if (root.Children.Count != 0)

               {

                   var s = string.Join("", root.Children.Select(Dump)).Split('\n');

                   var i = s.Length - 2;

                   for (; "│├└ ".Contains(s[i][0]); --i) s[i] = "  " + s[i];

                   s[i] = "└─" + s[i];

                   for (--i; i >= 0; --i) s[i] = ("│├└ ".Contains(s[i][0]) ? "│ " : "├─") + s[i];

                   head += string.Join("\n", s);

               }

               return head;

           }

  • Alternate, much simpler effort.

    Done as a series of state machines with triggers from the parent node node and transitions done as ti cascades.

    Obviously recursive (but your indication that wrapping doesn't matter would suggest that unless your using one of these dev.eyevis.net/.../EYE-LCD5600QHD_en.pdf).

    It will work on a shared node structure and will scale fine vertically and up to the stack bounds horizontally.

    It doesn't do string concatenation, only the (amortized constant in most cases) appends to the machine which is basically a 'stack with benefits'

    It has the advantage you can send it to any writer, not just a string

    It's probably equivalent to someone else's as I haven't been looking.

    sealed class Dumper

    {

    static public string Dump(Node root)

    {

    TextWriter writer = new StringWriter();

    DFS(root, new List<State>(), writer);

    return writer.ToString();

    }

    /* ... */

    private enum State

    {

    NonTrailingChild,

    Filler,

    TrailingChild,

    Blank,

    }

    private static void DFS(Node n, List<State> machine, TextWriter writer)

    {

    // run the state machine

    for (int i = 0; i < machine.Count; i++)

    {

    switch (machine[i])

    {

    case State.Blank:

    writer.Write("  "); break;

    case State.Filler:

    writer.Write("│ "); break;

    case State.NonTrailingChild:

    writer.Write("├─");

    machine[i] = State.Filler;

    break;

    case State.TrailingChild:

    writer.Write("└─");

    machine[i] = State.Blank;

    break;

    }

    }

    writer.WriteLine(n.Text);

    int index = machine.Count;

    machine.Add(State.NonTrailingChild);

    for (int i = 0; i < n.Children.Count; i++)

    {

    if (i == n.Children.Count - 1)

    machine[index] = State.TrailingChild;

    else

    machine[index] = State.NonTrailingChild;

    DFS(n.Children[i], machine, writer);            

    }

    machine.RemoveAt(index);

    }

    }

  • Nice question.

    I went for a very straightforward, recursive method.  I wanted to write a simple solution quickly.  I chose not to complicate the code by passing any extra information down in the recursive calls; opting instead to build the indentation each time.  If I were to use this for deeper trees, I might optimize that.  

    Posting the Dumper class only.

    sealed class Dumper

    {

    int level = 0;

    Dictionary<int, Tuple<int,int>> levelChildMap = new Dictionary<int, Tuple<int,int>> ();

    StringBuilder output = new StringBuilder();

    public string Dump(Node root)

    {

    level++;

    output.Append( root.Text );

    output.Append( Environment.NewLine );

    int children = root.Children.Count, currentChild=0;

    foreach(var child in root.Children)

    {

    currentChild++;

    levelChildMap[level] = new Tuple<int,int>(children, currentChild);

    for(int i=1; i<level; i++)

    output.Append(levelChildMap[i].Item2 < levelChildMap[i].Item1 ? "│ " : "  ");

    output.Append( currentChild < children ? "├─" : "└─" );

    Dump(child);

    }

    level--;

    return output.ToString();

    }

    }

  • My humble solution: http://pastebin.com/BXxV8Nez

    Not quite as short and simple as Eric's, but in the same spirit I believe.

  • I used simple stack to remember where in the tree I am and list for current path. No recursion was required as I didn't know how deep the tree will go.

    http://pastebin.com/tSAc6ja7

  • Gabe: Thanks for looking at it and converting.

    The "feature" I was talking about was "yield". Apparently, .Net DOES have this feature, which I didn't know. It's STILL a useful feature which no language should be without; just another point in favor of .Net. None of the other differences were fundamental -- mere syntax trivialities.

  • I went iterative, because I didn't know if this would be used where one can run into depth limits. I should have probably asked on this requirement first. I tried to make it as readable as possible, but I felt that with iterative I cannot come even close to a solution that someone would like to read. I do miss the parent property. I guess I wouldn't need the parent stack if I had it.

     sealed class Dumper {

       private Stack<int> child = new Stack<int>();

       private Stack<Node> parent = new Stack<Node>();

       static public string Dump(Node root) {

         Dumper d = new Dumper();

         return d.DoDump(root);

       }

       private string DoDump(Node root) {

         StringBuilder builder = new StringBuilder();

         builder.AppendLine(root.Text);

         if (root.Children.Any()) {

           StringBuilder indent = new StringBuilder();

           child.Push(0);

           parent.Push(root);

           do {

             builder.Append(indent.ToString());

             Node next = NextChild();

             if (IsLastChild()) builder.Append("└-");

             else builder.Append("├-");

             builder.AppendLine(next.Text);

             child.Push(child.Pop() + 1);

             if (next.Children.Any()) {

               if (IsNoChild()) indent.Append("  ");

               else indent.Append("│ ");

               parent.Push(next);

               child.Push(0);

             }

             while (child.Any() && IsNoChild()) {

               child.Pop();

               parent.Pop();

               if (indent.Length >= 2)

                 indent.Remove(indent.Length - 2, 2);

             }

           } while (child.Any());

         }

         return builder.ToString();

       }

       private Node NextChild() {

         return parent.Peek().Children[child.Peek()];

       }

       private bool IsNoChild() {

         return child.Peek() >= parent.Peek().Children.Count

           || child.Peek() < 0;

       }

       private bool IsLastChild() {

         return child.Peek() == parent.Peek().Children.Count - 1;

       }

     }

    I don't like the indent being a StringBuilder so much. I guess I could save some time when counting how much indentation steps to take back and then do it all at once after the loop. That would introduce another variable though.

    In any case, thanks for the challenge.

  • I wrote this to be "in the style of The Daily WTF".  I'm not sure if I did a good job or not, after a while the question "how can I make this rely more on array manipulation?" becomes fairly difficult.

    sealed class Dumper

       {

           const string VERTICAL = "│";

           const string TEE = "├";

           const string HORIZONTAL = "─";

           const string HOOK = "└";

           const string SPACE = " ";

           static public string Dump(Node root)

           {

               int breadth = MaxDepth(root) + 1;

               int depth = TotalDepth(root) + 1;

               string[,] grid = new string[breadth, depth];

               StringBuilder tree = new StringBuilder();

               int x = 0, y = 0;

               FillGrid(root, ref grid, ref x, ref y);

               for (y = 0; y < depth; y += 1)

               {

                   for (x = 0; x < breadth; x += 1)

                   {

                       if (grid[x, y] == null)

                       {

                           tree.Append(SPACE);

                       }

                       else

                       {

                           tree.Append(grid[x, y]);

                       }

                   }

                   tree.AppendLine();

               }

               return tree.ToString();

           }

           static private int MaxDepth(Node root)

           {

               Node n = root;

               int depth = 0;

               while (n.Children.Count > 0)

               {

                   depth += n.Text.Length + 1;

                   n = n.Children[0];                

               }

               if (depth == 0)

               {

                   return 0;

               }

               else

               {

                   return Math.Max(depth, MaxDepth(root.Children[0]));

               }

           }

           static private int TotalDepth(Node root)

           {

               Node n = root;

               int depth = 0;

               while (n.Children.Count > 0)

               {

                   depth += n.Children.Count;

                   n = n.Children[0];                

               }

               if (depth == 0)

               {

                   return 0;

               }

               else

               {

                   return depth + TotalDepth(root.Children[0]);

               }

           }

           static private void FillGrid(Node root, ref string[,] grid, ref int x, ref int y)

           {

               int verticals = 0;

               grid[x, y] = root.Text;

               if (root.Children.Count > 0)

               {

                   verticals = MaxDepth(root.Children[0]) + 1;

                   if (verticals > 1)

                   {

                       grid[x, y + 1] = TEE;

                       grid[x + 1, y + 1] = HORIZONTAL;

                       for (int i = 1; i < verticals; i += 1)

                       {

                           grid[x, (y + 1) + i] = VERTICAL;

                       }

                       if (x == 0)

                       {

                           grid[x, (y + verticals)] = VERTICAL;

                           grid[x, (y + verticals + 1)] = HOOK;

                           grid[x + 1, (y + verticals + 1)] = HORIZONTAL;

                       }

                       else

                       {

                           grid[x, (y + verticals)] = HOOK;

                           grid[x + 1, (y + verticals)] = HORIZONTAL;

                       }

                   }

                   else

                   {

                       grid[x, y + 1] = HOOK;

                       grid[x + 1, y + 1] = HORIZONTAL;

                   }

                   foreach (Node child in root.Children)

                   {

                       x += 2;

                       y += 1;

                       FillGrid(child, ref grid, ref x, ref y);

                       x -= 2;

                   }

               }

           }

       }

  • Well, all the maintainable ones were taken, so I went for clever (and functional) ;-)

    (note this is *not* how I code in IRL)

       sealed class Dumper

       {

           static public string Dump(Node root)

           {

               return root.Text + "\n" + DumpChildren( root, "" );

           }

           static private string DumpChildren(Node node, string indent)

           {

               return node.Children.Count > 0

                   ?   string.Join( "",  node.Children.Take(node.Children.Count - 1).ToList()

                           .ConvertAll( new Converter<Node, String>( child => string.Format("{0}├─{1}\n{2}", indent, child.Text, DumpChildren(child, indent + "│ ") ) ) ).ToArray() )

                       + string.Format("{0}└─{1}\n{2}", indent, node.Children.Last().Text, DumpChildren(node.Children.Last(), indent + "  ") )

                   : "";

           }

       }

  • Argh! That double spacing kills it - here's a pastebin version: http://pastebin.com/5mT6tJxD

    I'm sure it could be cleaned up a bit with some LINQ pixie dusty, but my LINQ is rusty and I only had while waiting for a C++ build to finish to do it!

Page 2 of 4 (51 items) 1234