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!

  • Ok - slightly cleaner version - using Aggregate: http://pastebin.com/K7VQYxhq

  • Last refinement, I promise (could now see how to factor the text+"\n" up to the top): http://pastebin.com/VbYxZe1z

  • Spoke too soon! http://pastebin.com/seQ5By6t - almost readable now.

    That's it - before I tweak it anymore. Eric I hate you (and I mean that in the best possible way).

  • BTW: My design criteria.

    I already mentioned that I allowed myself to be a little more "clever" simply because the "KISS" space was already well represented. However, I also wanted to do it in an entirely functional style, using only immutable constructs (so I didn't use StringBuilder, for example).

    There is a loss of efficiency as a result (insignificant in this example, but if scaled up it may become a problem). However I think I have still minimised the number of new string allocations (at least in this version: http://pastebin.com/NxnKEqsu - yes I couldn't resist it, sorry).

    While it started out ugly, as I iterated it a bit it got cleaner and cleaner. I think the last result (or perhaps the penultimate one) is perhaps as readable as the imperative versions (maybe more so if you're used to looking at functional code).

    Obviously, being functional, I had to go for recursion. If I was trying to do it iteratively (with an imperative approach) I would have had to maintain my own stack anyway. This could be minimised if there were parent pointers. That's the only time I would have missed them.

  • Eric, your solution is quite elegant, and along the same lines I was originally thinking. Rather than post a doppleganger, here's a functional version I came up with. It's a recursive implementation as well that uses a divide & conquer strategy.

    It relies on two streaming extension methods: UniqueFirst( ) and UniqueLast( ) which address the problem of "do something different with the first/last element of a sequence". This implementation isn't ideal for large trees, as the string allocation will rapidly become a significant fraction of the runnng time. It would, however, be fairly easy to restructure it to pass a StringBuilder around - I leave that as an exercise for others.

    Here's the code:

       sealed class Dumper

       {

           static public string Dump(Node root)

           {

               // Uncomment the ToArray() call if not using .NET 4.0

               return string.Join("\n", DumpLines(root)/*.ToArray()*/);

           }

           static private IEnumerable<string> DumpLines(Node node)

           {

               yield return node.Text; // return self first

               // apply different line-connectors to last child than the first

               // divide into equivalent subproblems, and recurse (divide+conquer)

               foreach (var line in node.Children.UniqueLast(

                   c => DumpLines(c).UniqueFirst(s => "├─" + s, s => "│ " + s),

                   c => DumpLines(c).UniqueFirst(s => "└─" + s, s => "  " + s))

                   .SelectMany(s => s))

                   yield return line;

           }

       }

       static class RecurseExt

       {

           // Applies the first() selector to the first item of the sequence, and other() to all others. Streams the results.

           public static IEnumerable<TR> UniqueFirst<T,TR>( this IEnumerable<T> seq, Func<T,TR> first, Func<T,TR> other )

           {

               using (var iter = seq.GetEnumerator())

               {

                   if (iter.MoveNext())

                       yield return first(iter.Current);

                   while (iter.MoveNext())

                       yield return other(iter.Current);

               }

           }

           // Applies the last() selector to the last item of the sequence, and other() to all others. Streams the results.

           public static IEnumerable<TR> UniqueLast<T,TR>( this IEnumerable<T> seq, Func<T,TR> other, Func<T,TR> last )

           {

               T current = default(T);

               using (var iter = seq.GetEnumerator())

               {

                   if (iter.MoveNext())

                   {

                       current = iter.Current;

                       while (iter.MoveNext())

                       {

                           yield return other(current);

                           current = iter.Current;

                       }

                       yield return last(current);

                   }

               }

           }

       }

  • Interestingly, after thinking about this on my drive home. I realized that I could have used Aggregate() instead of UniqueFirst() and UniqueLast() - but it would make the code that much harder to understand. So I'm going to stand by my implementation even though it's a bit more code.

    I also could have pushed the string.Join( ) call down into the DumpLines( ) method which would cut down on the total number of string allocations/concatenations. I'm just not sure it's worth the added complexity.

  • (I thought I posted this earlier, so apologies if I double post)

    Here is my solution.  I opted for a recursive solution because I find it natural for a recursive structure.  My main goal was obvious correctness and simplicity. As far as the parent pointers question, I barely noticed their abscence.  Very little data was necessary from up the tree, and it was easy enough to pass that data in.  From a time/space perspective, I used some extra space (tracking a flag and the indentation), but saved a (potentially) large numbers of tree traversals by precalculating it. I also opted for a StringWriter instead of a StringBuilder since using a StringWriter made it trivial to add an overload of Dump that would write directly to another output such as the console or a file instead of returning the resultant string.

    static string Dump(Node root)

    {

       StringWriter stringWriter = new StringWriter();

       stringWriter.WriteLine(root.Text);

       DumpChildren(root, stringWriter, string.Empty);

       return stringWriter.ToString();

    }

    private static void DumpChildren(Node node, TextWriter writer, string indent)

    {

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

       {

           Node child = node.Children[i];

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

           DumpRecursive(child, writer, indent, childIsLastOfParent);

       }

    }

    static void DumpRecursive(Node node, TextWriter writer, string indent, bool lastChildOfParent)

    {

       writer.Write(indent);

       WritePrefix(writer, lastChildOfParent);

       writer.WriteLine(node.Text);

       string childIndent = indent + (lastChildOfParent ?

       "  " : "│ ");

       DumpChildren(node, writer, childIndent);

    }

    private static void WritePrefix(TextWriter writer, bool lastChildOfParent)

    {

       if (lastChildOfParent)

       {

           writer.Write("└─");

       }

       else

       {

           writer.Write("├─");

       }

    }

  • Here's my attempt, I'd appreciate any feedback

    http://pastebin.com/UaVHXM7t

  • This is my solution, not sure its the most effecient

           static public string Dump(Node root)

           {

               var sb = new StringBuilder();

               var q = new Stack<KeyValuePair<Node, string>>();

               q.Push(new KeyValuePair<Node, string>(root, string.Empty));

               while (q.Count > 0)

               {

                   var node = q.Pop();

                   sb.AppendLine(node.Value + node.Key.Text);

                   for (var i = node.Key.Children.Count; i > 0; i--)

                       q.Push(new KeyValuePair<Node, string>(node.Key.Children[i - 1], node.Value.Replace("└─", "  ").Replace("├─","| ") + (i == node.Key.Children.Count ? "└─" : "├─")));

               }

               return sb.ToString();

           }

  • Here's my solution:

    sealed class Dumper

    {

       static public string Dump(Node root)

       {

           var sb = new StringBuilder();

           Dump(sb, root, new bool[] { });

           return sb.ToString();

       }

       static private void Dump(StringBuilder builder, Node node, bool[] isLast)

       {

           int level = isLast.Length;

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

           {

               if (i == level - 1)

                   builder.Append(isLast[i] ? "\u2514\u2500" : "\u251c\u2500");

               else

                   builder.Append(isLast[i] ? "  " : "\u2502 ");

           }

           builder.AppendLine(node.Text);

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

           {

               Dump(

                   builder,

                   node.Children[i],

                   isLast.Concat(new[] { i == node.Children.Count - 1 }).ToArray());

           }

       }

    }

  • I posted last week but I didn't see it show up, apologies if it turns out to be a double post.

    Design Considerations And Approach:

    I chose an iterative solution because I wanted to avoid potential stack overflows through an arbitrarily-deep tree being handed in. We don't have memory or size boundaries as a part

    of the code requirements except for the words 'arbitrary tree', so I chose to err on the side of taking up more space vs. blowing up the stack.

    Recursion would allow keeping our place in each node's child collection during a depth-first traversal, but an iterative approach needs to manage that on its own,

    so I created a small iterator wrapper for the Node objects that would handle that.  Nobody else needs to know about this class and there's no reason to extend it, so it's

    a nested private sealed class. It should just iterate over the node contents without mutating anything, so it only returns iterators for the children and only exposes Get

    properties.

    A stack of iterators represents how many open nodes we currently have, each of which manages their current position.

    Whether children are left to read in the current node's collection determines what kind of line is drawn for each child and their children.

    Because of the output format, I'm guaranteed one child per line throughout the diagram. Because the length of the ancestor lines connecting its children together depends on the

    structure of its children and their descendents, a depth-first approach is ideal (and because I'm writing the tree as I go).

    All parent line structures remain constant for a given child heirarchy, so a single string pattern for a given level in the heirarchy

    can be reused and concatenated with children fairly easily. I chose to store that information as a part of each iterator for ease of reuse and to pass that on

    to any children.

    I didn't miss having parent pointers, per se, because I was keeping the ancestor state contained and the Stack was enough of the current heirarchy to suit my purposes. This kind of

    thing could easily get confusing to understand, so I tried to minimize the cleverness as much as I could. Maybe I succeeded.

    sealed class Dumper

           {

               private const string OpenParent = "│ ";

               private const string ClosedParent = "  ";

               private const string NonEndChildOpening = "├─";

               private const string EndChildOpening = "└─";

               private sealed class NodeIterator

               {

                   private Node node;

                   private int index;

                   public bool HasMoreChildren { get; private set; }

                   public string Text { get { return node.Text; } }

                   public string AncestorState { get; private set; }

                   public NodeIterator(Node node) { this.node = node; this.AncestorState = string.Empty; this.HasMoreChildren = node.Children.Count > 0; }

                   public NodeIterator GetNextChild()

                   {                    

                       var nextChild = node.Children[this.index];

                       this.index++;

                       if (this.node.Children.Count <= this.index)

                           this.HasMoreChildren = false;

                       var childIterator = new NodeIterator(nextChild);

                       childIterator.AncestorState = string.Format("{0}{1}", this.AncestorState, this.HasMoreChildren ? Dumper.OpenParent : Dumper.ClosedParent);

                       return childIterator;

                   }

               }

               static public string Dump(Node root)

               {                                

                   var stringBuilder = new StringBuilder();                

                   var openNodes = new Stack<NodeIterator>();

                   var openNextChildNode = new Action<NodeIterator>((currentIterator) =>

                   {

                       var childIterator = currentIterator.GetNextChild();      

                       openNodes.Push(childIterator);

                       stringBuilder.Append(currentIterator.AncestorState);

                       stringBuilder.Append(currentIterator.HasMoreChildren ? Dumper.NonEndChildOpening : Dumper.EndChildOpening);

                       stringBuilder.AppendLine(childIterator.Text);

                   });

                   var rootIterator = new NodeIterator(root);

                   stringBuilder.AppendLine(rootIterator.Text);

                   openNodes.Push(rootIterator);

                   while (openNodes.Count > 0)

                   {

                       var currentNode = openNodes.Peek();

                       if (currentNode.HasMoreChildren)

                           openNextChildNode(currentNode);

                       else

                           openNodes.Pop();

                   }

                   return stringBuilder.ToString();

               }            

           }

  • Here is a solutions that:

    1. Not recursive (but has commented version of recursive solution)

    2. All string operations (concats) are done using String.Join and StringBuilder (note back-building of string using Lists's quick pre-pending)

    3. lazy LINQ-ed  - result is build only when aggregation is done

    4. 54 lines with comments :)

    http://pastebin.com/23YdYQA1

    sealed class Dumper

           {            

               public static string Dump(Node root)

               {

                   // get all nodes (used later for "to parent" iteration

                   var allNodeTuples = EnumerateNodes(root, null);

                   // main query, later we'll agregate results

                   var query = allNodeTuples.Select(tuple =>

                   {

                       var node = tuple.Item1;

                       var parent = tuple.Item2;

                       var s = new List<string> {node.Text, Environment.NewLine};

                       if (parent != null)

                       {

                           // thats for 'closest' childs

                           s.Insert(0, parent.Children.Last() != node ? "├" : "└");

                           s.Insert(1,"-");

                           do

                           {

                               // build indention

                               node = parent;

                               var oldParent = parent;

                               parent = allNodeTuples.Where(t => t.Item1 == oldParent).FirstOrDefault().Item2;

                               if (parent != null)                            

                                   s.Insert(0, (parent.Children.Last() != node

                                                    ? "│ "

                                                    : "  "));                            

                           } while (parent != null);

                       }

                       // joins results into single line

                       return string.Join(String.Empty,s);

                   });                

                   // run query with string builder to aggregate

                   return query.Aggregate(new StringBuilder(), (s, v) => s.Append(v)).ToString();

               }

               // Enumerate all tree nodes, returning tuple with first item as node, second as node's parent

               private static IEnumerable<Tuple<Node,Node>> EnumerateNodes(Node root, Node parent)

               {

                   /* recursive:

                   yield return new Tuple<Node,Node>(root, parent);

                   foreach (var child in root.Children)

                       foreach (var sub in EnumerateNodes(child, root)) yield return sub;*/                                

                   var workStack = new Stack<Tuple<Node,Node>>();

                   workStack.Push(new Tuple<Node, Node>(root, parent));

                   while (workStack.Count>0)

                   {

                       var current = workStack.Pop();

                       yield return current;

                       foreach (var child in current.Item1.Children.Reverse())

                           workStack.Push(new Tuple<Node, Node>(child, current.Item1));

                   }

               }          

           }

  • Used a stack and recursion - designed for readability over performance.

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

    namespace FAIC.OldSchoolTreeDisplay

    {

       sealed class Dumper

       {

           private static Stack<string> _indents = new Stack<string>();

           private static StringBuilder _sb = new StringBuilder();

           static public string Dump(Node root)

           {

               DumpInternal(root);

               return _sb.ToString();

           }

           static private void DumpInternal(Node node)

           {

               _sb.AppendLine(node.Text);

               if (node.Children.Count > 0)

               {

                   node.Children

                       .Take(node.Children.Count - 1)

                       .ForEach(child =>

                       {

                           // print the indents first

                           _indents.Reverse().ForEach(indent => _sb.Append(indent));

                           // then print the pointer

                           _sb.Append("├─");

                           _indents.Push("│ ");

                           DumpInternal(child);

                           _indents.Pop();

                       });

                   // print the indents first

                   _indents.Reverse().ForEach(indent => _sb.Append(indent));

                   // then print the pointer

                  _sb.Append("└─");

                  _indents.Push("  ");

                   DumpInternal(node.Children.Last());

                   _indents.Pop();

               }

           }

       }

       internal static class Helpers

       {

           public static void ForEach<T>(this IEnumerable<T> stuff, Action<T> action)

           {

               foreach (var s in stuff)

               {

                   action(s);

               }

           }

       }

    }

  • class Dumper

       {

           static string[][] ar = new string[][]{new []{ "├─", "| " },new []{ "└─", "  " }};

           private static string Dump(Node root, string prefix = "")

           {

               var str = root.Text + "\r\n";

               for (var i = 0; i < root.Children.Count; i++)

               {

                   var pos = root.Children.Count - 1 == i ? 1 : 0;

                   str += prefix + ar[pos][0] + Dump(root.Children[i], prefix + ar[pos][1]);

               }

               return str;

           }

       }

  •    sealed class Dumper

       {

           static public string Dump(Node root)

           {

               return root.Text + "\n" + string.Join("\n", DumpLine(root));

           }

           static IEnumerable<string> DumpLine(Node node)

           {

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

               {

                   var isLast = i == node.Children.Count - 1;

                   yield return (isLast ? "└─" : "├─") + node.Children[i].Text;

                   foreach (var child in DumpLine(node.Children[i]))

                       yield return (isLast ? "  " : "│ ") + child;

               }

           }

       }

Page 3 of 4 (51 items) 1234