Old school tree display


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!


Comments (51)

  1. James Dunne says:

    Very cool challenge, Eric! I too have put together my own algorithm-oriented developer challenge while we were in "interview / hiring" mode a few months back. I was never satisfied with the approach of asking insanely technical questions and getting back canned answers, so I wanted to present a unique, non-standard way of gauging interviewee skills where one simply cannot fake it. I have not subjected any candidate to this test but it's something I have on the back-burner. I would be very interested in your thoughts on this exercise, sir!

    http://bittwiddlers.org/?p=87

  2. M.E. says:

    Here's my first stab at it. Admittedly it does some extra work because it regenerates the "indent" each time, but on the plus side, it's aware of where it is in the tree so it could do additional things with that information. I opted for an iterative approach because I think it's easier to debug and so forth.

    static class Dumper {

    const string BarSep = " ";

    const string BranchSep = "─";

    const string Bar = "│";

    const string Branch = "├";

    const string LastBranch = "└";

    struct NodeAndLevel {

    public Node Node;

    public List<bool> Level;

    }

    static public string Dump(Node root) {

    Stack<NodeAndLevel> stack = new Stack<NodeAndLevel>();

    stack.Push(new NodeAndLevel { Node = root, Level = new List<bool>() });

    StringBuilder builder = new StringBuilder();

    while(stack.Count > 0) {

    NodeAndLevel l = stack.Pop();

    foreach (var graphic in l.Level.SelectCheckLast<bool, string>(DumpSingleLevel)) {

    builder.Append(graphic);

    }

    builder.AppendLine(l.Node.Text);

    foreach (var nodeAndLevel in l.Node.Children.SelectCheckLast((isLast, child) => new NodeAndLevel { Node = child, Level = new List<bool>(l.Level) { isLast } }).Reverse()) {

    stack.Push(nodeAndLevel);

    }

    }

    return builder.ToString();

    }

    static string DumpSingleLevel(bool isBranch, bool isLast) {

    if(isBranch)

    return (isLast ? LastBranch : Branch) + BranchSep;

    return (isLast ? BarSep : Bar) + BarSep;

    }

    static IEnumerable<TOut> SelectCheckLast<TIn, TOut>(this IList<TIn> source, Func<bool, TIn, TOut> selector) {

    if(source.Count == 0)

    yield break;

    for (int i = 0; i < source.Count – 1; i++)

    yield return selector(false, source[i]);

    yield return selector(true, source[source.Count – 1]);

    }

    }

  3. James Dunne says:

    Why not have the Dump method return an IEnumerable<string> to imply a line-by-line solution, intended for generic output. Is this intended for console output or file output? Do we have a console maximum column width with which to impose word-wrapping logic upon? That would certainly allow for "prettier" formatting line-by-line so you can describe the output in terms of word-wrapped lines where each line would be able to start with the appropriate "box drawing" characters to indicate proper tree depth rather than an assumed count of spaces, or worse, no spaces and relying on the default console line wrapping.

    Good questions. This is actually not just an idle exercise; I wrote this challenge because I wrote this code myself for a real purpose. I am writing a code analysis tool in C# that requires that I build up a number of large, complicated trees in memory. I wanted a way to be able to dump a whole or partial tree as a string at once into the debugger "text viewer" window, so that I could rapidly ensure that the tree was the shape I expected. The trees will typically be shallow and broad, so I am not too worried about word-wrap. – Eric

  4. Joren says:

    My attempt. I haven't looked at your code at all yet, so I'm pretty curious where it differs. My intent was to go for obvious correctness.

    Since recursion naturally drives you to mostly ignore everything except the current node and its children, I chose to make each node responsible for printing its own name and all its descendents, nothing more. However, I allowed myself to stray from that (a bit more cleverness here, instead of obviousness), by having each node also handle indentation that doesn't really have anything to do with it. This is so that I can keep appending characters left-to-right, instead of using a far more complicated system to insert characters at arbitrary positions.

    I didn't miss having parent pointers at all. I do a depth-first recursion, and whenever I do that I carry any information from the parent just by passing it through the method parameters.

    My other design considerations are hopefully apparent from my code comments.

    sealed class Dumper

    {

       public static string Dump(Node root)

       {

           // A StringBuilder is more convenient than manual concatenation.

           StringBuilder sb = new StringBuilder();

           Dump(root, sb, "");

           return sb.ToString();

       }

       // We're taking a depth-first recursive solution, because that naturally follows the

       // structure of both the Node class and the desired output string. If it does not perform

       // well, or blows the stack, it would be easy enough to convert it to an iterative form.

       // We have the recursive method append its results to the StringBuilder we pass it, so that

       // we don't allocate an arbitrarily large amount of StringBuilders.

       //

       // The indentation string functions as a stack of characters to add on each line.

       // We do not otherwise have enough information to tell if we should print '│' characters,

       // because it depends on the amount of children our ancestors have.

       //

       // The immutability of the String class makes it ideal for this purpose, since we do not

       // have to worry about popping anything off the stack when returning to lower levels in the

       // recursion.

       private static void Dump(Node node, StringBuilder builder, string indentation)

       {

           var children = node.Children;

           builder.AppendLine(node.Text);

           // If we have no children at all, we're done.

           if (children.Count == 0)

               return;

           for (int i = 0; i < children.Count – 1; i++)

           {

               // Indent appropriately to the depth of the current Node.

               builder.Append(indentation);

               // For every child that is not the last, print "├─" .

               builder.Append("├─");

               // Then print the child, increasing the indentation by "│ ".

               Dump(children[i], builder, indentation + "│ ");

               // The child will entirely take care of all the lines that contain its own

               // children, so the current child has now been entirely handled.

           }

           // Indent appropriately to the depth of the current Node.

           builder.Append(indentation);

           // For the last child, print "└─" instead of "├─".

           builder.Append("└─");

           // We already have a line of │ connecting all our children. We have no children left,

           // so now we indent with only spaces.

           Dump(children[children.Count – 1], builder,  indentation + "  ");

       }

    }

  5. carlos says:

    Recursive because it's short and simple.

    static public string Dump(Node root)

    {

       StringBuilder sb = new StringBuilder();

       DoDump(sb, "", "", root);

       return sb.ToString();

    }

    static private void DoDump(StringBuilder sb, string prefixRoot, string prefixChild, Node root)

    {

       sb.Append(prefixRoot);

       sb.Append(root.Text);

       sb.Append('n');

       for (int i = 0; i != root.Children.Count; ++i)

       {

           if (i == root.Children.Count – 1)

           {

               // Final child

               DoDump(sb, prefixChild + "└─", prefixChild + "  ", root.Children[i]);

           }

           else

           {

               // Not final child

               DoDump(sb, prefixChild + "├─", prefixChild + "│ ", root.Children[i]);

           }

       }

    }

  6. Shuggy says:

    quick and dirty.

    sealed class Dumper
    {
      static public string Dump(Node root)
      {
        TextWriter writer = new StringWriter();
        Action<Node> requestParentWrite = n => {}; // no-op
        DFS(root, requestParentWrite, writer);
        return writer.ToString();
      }
    /* … */
      private static void DFS(Node n, Action<Node> requestParentWrite, TextWriter writer)
      {
        requestParentWrite(n);
        writer.WriteLine(n.Text);
        string nonDirectChildren = "│ ";
        Action<Node> newRequestParentWrite = (actual) =>
        {
          requestParentWrite(actual);
          if (n.Children.Contains(actual))
          {
            if (n.Children.Last() == actual)
            {
              writer.Write("└");
              nonDirectChildren = "  ";
            }
            else
            {
              writer.Write("├");
            }
            writer.Write("─");
          }
          else
          {
            writer.Write(nonDirectChildren);
          }
        };
        for (int i = 0; i < n.Children.Count; i++)
          DFS(n.Children[i], newRequestParentWrite, writer);             
      }
    }

    I note two assumptions here. First, that repeatedly searching the child list for a particular node is efficient; if the tree is very broad and shallow then this becomes a quadratic algorithm. And second, that nodes are not re-used. In immutable trees it is commonplace to re-use nodes; what happens if the same node is referred to in both the first and second positions of a parent with two children? – Eric

  7. carlos says:

    I'm surprised no-one has posted the shortest meets-the-literal-specification solution:

    static public string Dump(Node root)
    {
       return "an├─bn│ ├─cn│ │ └─dn│ └─en│   └─fn└─gn  ├─hn  │ └─in  └─jn";
    }

    Do you by any chance write video card drivers? – Eric

  8. Ben says:

    Here's mine: I decided that I didn't want to pass any information to lower levels, so each level of recursion indents the whole subtree that was returned, simply because the correct tree "growing" out of the simple single indents seems the most elegant to me. I used a trailing loop to make the code a bit more flexible: we have an IList, but I wanted to make sure it would work if it was IEnumerable instead. And finally, I used iterator blocks because they allow me to write this recursive code that makes sense to me, but which in the end gets turned into (effectively) a single loop over the nodes.

    sealed class Dumper

    {

       static public string Dump(Node root)

       {

           StringBuilder sb = new StringBuilder();

           foreach (string s in DumpLines(root))

           {

               sb.AppendLine(s);

           }

           return sb.ToString();

       }

       static public IEnumerable<string> DumpLines(Node root)

       {

           yield return root.Text;

           IEnumerable<string> last = null;

           foreach (Node node in root.Children)

           {

               if (last != null)

               {

                   foreach (string line in Indent(last, "├─", "│ "))

                   {

                       yield return line;

                   }

               }

               last = DumpLines(node);

           }

           if (last != null)

           {

               foreach (string line in Indent(last, "└─", "  "))

               {

                   yield return line;

               }

           }

       }

       private static IEnumerable<string> Indent(IEnumerable<string> lines, string first, string rest)

       {

           bool isFirst = true;

           foreach (string line in lines)

           {

               if (isFirst)

               {

                   yield return first + line;

                   isFirst = false;

               }

               else

               {

                   yield return rest + line;

               }

           }

       }

    }

  9. Gabe says:

    Straightforward DFS recursive solution. In order to maintain state, I pass along a boolean array "isLastPath", which contains an entry for every node in the current path (excluding the root) – true if that ancestor is the last child of its parent, false otherwise.

    http://gist.github.com/572285

  10. Olivier says:

    I wrote this. (Sorry that the language is not C#, though translation should be obvious.)

    def show(text, blist)

     if blist.size == 0

       puts text

     else

       s = blist[0..-2].map{|b| b ? "| " : "  "}.join

       puts(s + (blist[-1] ? "+" : "\") + "-" + text)

     end

    end

    def dump(node, blist = [])

     show(node.text, blist)

     blist.push true

     for n in node.children

       blist[-1] = n != node.children.last

       dump(n, blist)

     end

     blist.pop

    end

    Ah, I am ashamed, for your solution is simpler. String being an immutable value type beats using a list of bool.

    Also, I notice that you did not separate the iterating and printing logic, but there's no point to it in such a small example.

    Here's the rest of the code, for testing.

    class Node

    attr_accessor :text, :children

    def initialize(text, *children)

    @text, @children = text, children

    end

    end

    n = Node.new("a",

    Node.new("b",

    Node.new("c", Node.new("d")),

    Node.new("e", Node.new("f"))),

    Node.new("g",

    Node.new("h", Node.new("i")),

    Node.new("j")))

    dump(n)

  11. Jeffrey L. Whitledge says:

    I actually wrote this very thing a few months ago for a project that I was working on. (I also wrote something similar last year, which was just for binary trees, and had the parent on the middle left and the children above right and below right.)

    Here's my version adapted to this excersize:

           static public string Dump(Node root)

           {

               StringBuilder sb = new StringBuilder();

               DumpCore(root, sb, string.Empty, string.Empty);

               return sb.ToString();

           }

           static private void DumpCore(Node node, StringBuilder sb, string initialPrefix, string followingPrefix)

           {

               sb.Append(initialPrefix);

               sb.Append(node.Text);

               sb.AppendLine();

               if (node.Children.Count == 0)

                   return;

               string nextInitialPrefix = followingPrefix + "├─";

               string nextFollowingPrefix = followingPrefix + "│ ";

               string lastInitialPrefix = followingPrefix + "└─";

               string lastFollowingPrefix = followingPrefix + "  ";

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

                   if (childIndex < node.Children.Count – 1)

                       DumpCore(node.Children[childIndex], sb, nextInitialPrefix, nextFollowingPrefix);

                   else

                       DumpCore(node.Children[childIndex], sb, lastInitialPrefix, lastFollowingPrefix);

           }

    I went with the recursive solution, because it was the most obvious. I was just going for simplicity. I never even considered parent pointers. My approach was basically to draw a tree in notepad and then figure out the essense of the problem and create the simplist design I could that embodied that essense.

  12. Jeffrey L. Whitledge says:

    I should read my code before I post it!

    I should definitely have taken the if-statement out of the loop. I'm guessing that is an unfortunate artifact of an early unsuccessful design.

  13. Gabe says:

    I tried to come up with some ideas for how you could use a parent pointer, but I couldn't think of anything useful to do with it off the top of my head. I was able to come up with a purely functional approach to the problem, though (with a bit of augmentation to LINQ):

       static class Dumper

       {

           const string vbar = "│ ", hbar = "─", branch = "├" + hbar, corner = "└" + hbar, blank = "  ";

           static public string Dump(Node root)

           {

               return Dump(root, Enumerable.Empty<bool>());

           }

           static public string Dump(Node root, IEnumerable<bool> isLastPath)

           {

               return string.Join("",

               // draw vertical bars for parent nodes

                       isLastPath.Take(isLastPath.Count() – 1).Select(isLast => isLast ? blank : vbar)

               // draw connector for current node

               .Concat(isLastPath.Any() ? (isLastPath.Last() ? corner : branch) : "")

               // text for this node

               .Concat(root.Text)

               // new line

               .Concat(Environment.NewLine)

               // recurse for child nodes

               .Concat(root.Children.Select((node, index) => Dump(node, isLastPath.Concat(index == root.Children.Count – 1)))));

           }

           // sadly, LINQ doesn't include the "return" part of the IEnumerable monad, so we make a Concat that accepts a scalar

           public static IEnumerable<T> Concat<T>(this IEnumerable<T> list, T item)

           {

               foreach (T i in list)

                   yield return i;

               yield return item;

           }

       }

    Coincidentally, the other Gabe came up with a similar solution (using isLast) while I was writing mine.

  14. Weeble says:

    Here's mine, without looking at yours or any of the others just yet (posting it on PasteBin because I am afraid of what your blog is going to do to the formatting):

    http://pastebin.com/KJLvqgRj

    My design criteria:

    * It should be a small amount of code. As much as I love coding, I hate code.

    * It should not take me long to write. (I considered using LINQ to objects, but I ruled it out because I was not confident that I could do it quickly without hitting a snag – in particular I was worried about whether it would be easy to treat the last child specially without having to write an entire extra method, and about how I would assemble the string. I think both are possible, but I could have easily seen me wasting 20 minutes looking stuff up.)

    I'm not sure I did very well on these counts. The only thing worth mentioning there is that my first attempt was wrong and printed extraneous vertical bars to the left of children of a last child. When I fixed that I ended up with an if statement in the middle of the loop to check whether we were at the last child and if so tweak our prefix and children's prefixes. I didn't like the extra indentation and the assignments in different branches. After some humming and hawing I decided that two uses of the conditional operator were preferable to the if statement, since it reduced the number of assignments and the indentation of the code. I find it's slightly nicer to read, but that might be very subjective.

  15. Maciej says:

    Hm no iterative BFS so far?

    Here you are.

    sealed class Dumper

    {

       static public string Dump(Node root)

       {

           StringBuilder output = new StringBuilder();

           foreach(string line in subTreePicture(root))

           {

               output.Append(line);

               output.Append('n');

           }

           return output.ToString();

       }

       private struct NodesAndPrefix

       {

           public LinkedListNode<string> listNodeToAddAfter;

           public Node treeNode;

           public string prefix;

           public NodesAndPrefix(LinkedListNode<string> listNodeToAddAfter, Node treeNode, string prefix)

           {

               this.listNodeToAddAfter = listNodeToAddAfter;

               this.treeNode = treeNode;

               this.prefix = prefix;

           }

       }

       static private IEnumerable<string> subTreePicture(Node root)

       {

           LinkedList<string> thePicture = new LinkedList<string>();

           Queue<NodesAndPrefix> queueOfNodesToProcess = new Queue<NodesAndPrefix>();

           LinkedListNode<string> listNode = thePicture.AddLast(root.Text);

           queueOfNodesToProcess.Enqueue(new NodesAndPrefix(listNode, root, ""));

           while(queueOfNodesToProcess.Count > 0)

           {

               NodesAndPrefix nextItem = queueOfNodesToProcess.Dequeue();

               LinkedListNode<string> nodeToAddAfter = nextItem.listNodeToAddAfter;

               IList<Node> children = nextItem.treeNode.Children;

               int lastIndex = children.Count – 1;

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

               {

                   nodeToAddAfter = thePicture.AddAfter(nodeToAddAfter,

                       nextItem.prefix + "├─" + children[i].Text);

                   queueOfNodesToProcess.Enqueue(new NodesAndPrefix(nodeToAddAfter,

                       children[i], nextItem.prefix + "│ "));

               }

               if(lastIndex >= 0)

               {

                   nodeToAddAfter = thePicture.AddAfter(nodeToAddAfter,

                       nextItem.prefix + "└─" + children[lastIndex].Text);

                   queueOfNodesToProcess.Enqueue(new NodesAndPrefix(nodeToAddAfter,

                       children[lastIndex], nextItem.prefix + "  "));

               }

           }

           return thePicture;

       }

    }

  16. Michael McMullen says:

    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;

                   }

               }

           }

  17. ErikF says:

    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();

     }

    }

  18. 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.

  19. mcherm says:

    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.

  20. Gabe says:

    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;

               }

           }

       }

  21. xaos says:

    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;

           }

  22. Shuggy says:

    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);

    }

    }

  23. Winston Smith says:

    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();

    }

    }

  24. Allon Guralnek says:

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

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

  25. Toni Petrina says:

    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

  26. mcherm says:

    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.

  27. Anonymous says:

    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.

  28. Aaron says:

    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;

                   }

               }

           }

       }

  29. Phil Nash says:

    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 + "  ") )

                   : "";

           }

       }

  30. Phil Nash says:

    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!

  31. Phil Nash says:

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

  32. Phil Nash says:

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

  33. Phil Nash says:

    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).

  34. 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.

  35. Leo Bushkin says:

    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);

                   }

               }

           }

       }

  36. Leo Bushkin says:

    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.

  37. Chris B says:

    (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("├─");

       }

    }

  38. configurator says:

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

    http://pastebin.com/UaVHXM7t

  39. Martin Booth says:

    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();

           }

  40. Thomas Levesque says:

    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] ? "u2514u2500" : "u251cu2500");

               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());

           }

       }

    }

  41. Chris Hannon says:

    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();

               }            

           }

  42. Olostan says:

    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));

                   }

               }          

           }

  43. David Cuccia says:

    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);

               }

           }

       }

    }

  44. AmunRA82 says:

    class Dumper

       {

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

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

           {

               var str = root.Text + "rn";

               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;

           }

       }

  45. Mitsu says:

       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;

               }

           }

       }

  46. Lost_Soul says:

    First i did it nearly similar, then i thought about using LINQ to solve it:

    sealed class Dumper

    {

          public static string Dump(Node root)

          {

              return Dump(root, "");

          }

         private static string Dump(Node nod, string str)

          {

              return nod.Children.Aggregate(nod.Text,

                                          (s, n) =>

                                          s + "n" + str + (n == nod.Children.Last() ? "└─" : "├─") +

                                          Dump(n, str + (n == nod.Children.Last() ? "  " : "│ ")));

          }

    }

    Hope there's no error in it.

  47. Alexey Kurakin says:

    I wrote somewhat similar code to Eric's solution, and very close to the solution of person with nick Weeble:

       sealed class Dumper

       {

           public const char Cross = 'u251c';    // |-

           public const char EndCross = 'u2514'; // |_

           public const char Line = 'u2502';     // |

           public const char Space = ' ';

           static public string Dump(Node root)

           {

               if (root == null) return string.Empty;

               StringBuilder builder = new StringBuilder();

               StringBuilder prefix = new StringBuilder();

               builder.AppendLine(root.Text);

               DrawChildren(builder, prefix, root);

               return builder.ToString();

           }

           private static void DrawChildren(StringBuilder builder, StringBuilder prefix, Node node)

           {

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

               {

                   bool isLast = i == node.Children.Count – 1;

                   builder.Append(prefix.ToString());

                   builder.Append(isLast ? EndCross : Cross);

                   builder.AppendLine(node.Children[i].Text);

                   prefix.Append(isLast ? Space : Line);

                   DrawChildren(builder, prefix, node.Children[i]);

                   prefix.Length = prefix.Length – 1;

               }

           }

       }

    But instead of string prefix, I used StringBuilder. Could you please comment whether appoach with StringBuilder for prefix is better than string? And why?

  48. Ann Onymouse says:

    Very nice to hear that you're an old C64 programmer. :)

  49. Alexander says:

    There is a procedure that uses two instances of the StringBuilder to consume less memory on the line indent.

    static public string Dump(Node root)

    {

    var result = new StringBuilder();

    var indent = new StringBuilder();

    Action<Node> dumpNode = null;

    dumpNode = node =>

    {

    result.AppendLine(node.Text);

    var lastIndex = node.Children.Count – 1;

    for (var i = 0; i < lastIndex; i++)

    {

    result.Append(indent);

    result.Append("├─");

    indent.Append("│ ");

    dumpNode(node.Children[i]);

    indent.Length = indent.Length – 2;

    }

    if (lastIndex >= 0)

    {

    result.Append(indent);

    result.Append("└─");

    indent.Append("  ");

    dumpNode(node.Children[lastIndex]);

    indent.Length = indent.Length – 2;

    }

    };

    dumpNode(root);

    return result.ToString();

    }

  50. Mr. TA says:

    If not too late…

    string Output(Node root)

    {

    var sb = new StringBuilder();

    Output(sb, root, new bool[0]);

    return sb.ToString();

    }

    void Output(StringBuilder sb, Node node, bool[] levels)

    {

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

    {

    bool b = levels[i];

    if (i < levels.Length – 1)

    {

    if (b)

    {

    sb.Append("│ ");

    }

    else

    {

    sb.Append("  ");

    }

    }

    else

    {

    if (b)

    {

    sb.Append("├─");

    }

    else

    {

    sb.Append("└─");

    }

    }

    }

    sb.AppendLine(node.Text);

    foreach (var child in node.Children)

    {

    Output(sb, child, levels.Concat(new[] { child != node.Children.Last() }).ToArray());

    }

    }

  51. Ramesh vel says:

    static public string Dump(Nodee root)

           {

               int count = 0;

               string dumStr = root.Text;

               dumStr += DumpIn(root.Children, count);            

               return dumStr;

           }

           private static string DumpIn(IList<Nodee> root, int count)

           {

               string dumStr = "";

               foreach (var nod in root)

               {

                   dumStr += 'n' + count.Times("│ ") + ((nod.Children.Count == 0) ? "└─" : "├─") + nod.Text;              

                   dumStr += DumpIn(nod.Children, count + 1);                              

               }

               return dumStr;

           }

           static string Times(this int src,string ch)

           {

               string res = "";

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

               {

                   res += ch;

               }

               return res;

           }