2010
09.11

Eric Lippert has put a little problem up on his blog – Old school tree display; here’s how I got to a solution.

First, examine the desired output:

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

We’re going to be doing a depth-first tree traversal. Recursion seems like the easiest way to go. We need to return a string – building up a string like this naturally suggests a StringBuilder. Just to confirm I can remember back to dealing with trees at university, first just print out the traversal:

public static string Dump(Node root)
{
   StringBuilder nodeDump = new StringBuilder();
   Dump(root, nodeDump);

   return nodeDump.ToString();
}

private static void Dump(Node node, StringBuilder nodeDump)
{
   nodeDump.AppendLine(node.Text);
   foreach(var child in node.Children)
   {
      Dump(child, nodeDump);
   }
}

Phew, I haven’t forgotten everything, we get the right output:

a
b
c
d
e
f
g
h
i
j

So all that’s missing are the tree lines. This first pass has got the first line correct though, so there’s no need to change that. Some “stuff” needs adding to the loop. The first thing I notice is that the last child of a node is preceded by a └, whereas the other children are preceded by a ├. So we need to test whether we’re dealing with the last child. This is going to be easier to do with a plain old for loop rather than using foreach.

So, let’s see if I can get the correct symbol to be printed before each node:

private static void Dump(Node node, StringBuilder nodeDump)
{
   nodeDump.AppendLine(node.Text);
   for(int i = 0; i < node.Children.Count; i++)
   {
      if(i + 1 == node.Children.Count)
      {
         nodeDump.Append('└');
      }
      else
      {
         nodeDump.Append('├');
      }
      
      nodeDump.Append('─');
      
      Dump(node.Children[i], nodeDump);
   }
}

This gives

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

Ok, so now all that’s missing are the spaces and vertical lines. This needs to be done before appending the lines we’ve already got. Thanks to the magic of recursion, we only need to care about the prefix text for the current node in the loop.

If we’re dumping the last child, it’ll be prefixed by two spaces. If not, it’ll be prefixed by a │ and a space. This will be in addition to whatever prefix is passed into the method. This means the Dump method needs to take another paramter, prefix. For the root node this is going to be the empty string.

At the same time, the test for the last child is a bit ugly. As we now need to know if we’ve got the last child in two places, this if/else can be collapsed into a bool variable, and the tests can use the conditional operator, which will be much neater.

public static string Dump(Node root)
{
   StringBuilder nodeDump = new StringBuilder();
   Dump(root, nodeDump, String.Empty);
   
   return nodeDump.ToString();
}

private static void Dump(Node node, StringBuilder nodeDump, string prefix)
{
   nodeDump.AppendLine(node.Text);
   for(int i = 0; i < node.Children.Count; i++)
   {
      bool isLastChild = i + 1 == node.Children.Count;
      nodeDump.Append(prefix);
      nodeDump.Append(isLastChild ? '└' : '├');
      nodeDump.Append('─');
      
      Dump(node.Children[i], nodeDump, prefix + (isLastChild ? "  " : "│ "));
   }
}

It works!

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

No Comment.

Add Your Comment