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!

  • 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

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

    }

    }

  • 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

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

       }

    }

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

           }

       }

    }

  • 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

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

    static public string Dump(Node root)
    {
       return "a\n├─b\n│ ├─c\n│ │ └─d\n│ └─e\n│   └─f\n└─g\n  ├─h\n  │ └─i\n  └─j\n";
    }

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

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

               }

           }

       }

    }

  • 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

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

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

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

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

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

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

       }

    }

Page 1 of 4 (51 items) 1234