Creating an ASCII-art tree in C#

I recently made my first pull request to the Cake project in which I added a command line option (--showtree) to display the tasks in a Cake script in a tree view.

Creating the tree view itself took me a couple of attempts to get right, and I'm bound to forget the trick for it, so in this post I'm going to show the code required to create a similar tree diagram in your own program.

If you're not here for the chit-chat, and you just want the code, feel free to jump ahead. Alternatively, take a look at the real code in the Cake project, or this Stack Overflow question which follows a similar approach. You can also see Immo Landwerth recreate a similar tree in his recent video on building a compiler. I highly recommend you check out that last link either way, it's excellent!

Requirements for the data structure

Before we look at the tree itself, it's worth considering the data structure you need to build this tree. There's basically two requirements:

Enumerate all the "top-level" or "root" nodes, i.e. those nodes that are not a child of any other node
For each node, enumerate (and count) the immediate child nodes

Ideally, your data structure will look similar to the tree diagram you're building, but that's not required. As a simple example, we'll consider nodes like the following:

class Node
{
    public string Name { get; set; }
    public ICollection<Node> Children { get; } = new List<Node>();
}

We also have a function that returns an IEnumerable<> of the "top level" nodes. This function would create the node "graph" for you, and will depend on your specific application.

IEnumerable<Node> topLevelNodes = CreateNodeList();

I've made a point of using both ICollection<> and IEnumerable<> here, as it highlights the difference in requirements between the list of top-level nodes, and the list of a node's children. We don't need care how many top-level nodes there are, we just need to be able to enumerate through them, hence using IEnumerable<>. On the other hand we do need to be able to find the number of child nodes a given node has (you'll see why shortly), hence using ICollection<> which exposes Count.

Technically, we don't need to know how many child nodes a parent node has. We just need to be able to tell, while enumerating the child nodes, when we've reached the final node.

That's all there is on the data side, which should be pretty flexible. Depending on the data you're trying to display, these data structures may already be available to you, or you may need to build them up manually. For the Cake PR I had to do a bit of both - ScriptHost.Tasks lets you retrieve the children of any given task, but to find the top-level tasks I used an instance of CakeGraphBuilder instead.

Requirements for the display algorithm

As a brief reminder, the ascii structure we're trying to recreate is something like the following:

Default
 └─Package
    ├─Zip-Files
    │  ├─Generate-Hashes
    │  │  └─Validate-Zip-Files
    │  └─Copy-Files
    │     └─Run-Unit-Tests
    └─Create-Nuget-Packages
       └─Build
          └─Restore-Nuget-Packages

The corners and cross piece characters are part of "extended ASCII", commonly known as "box-drawing" or "line-drawing" characters. You could also use ordinary hyphens “-” and pipes “|”, but I think the box-drawing characters make the tree more readable. I used codes 179 “│” , 192 “└”, and 195 “├” from here.

When I first took a stab at drawing the ASCII art tree, I dove right in and started writing code without thinking to much about exactly what I needed to display. It didn't seem like it should be a hard problem to solve with a little recursion.

Unfortunately, the results weren't quite right - some vertical lines were missing, or there were extra ones where there shouldn't be. After floundering a couple of times, I took a step back, and thought about the characteristics of the diagram:

Top-level tasks should not be indented or prefixed
Child nodes are indented based on their depth from the top-level node
If a node is the last child it should have a corner (└) prefix, otherwise it should have a crosspiece prefix (├)
If any parent node was not the last child, a pipe (│) prefix is required in the correct position

That last point was the one that was scuppering my initial attempts; not only does every node need to know its own position in the tree (is it the last child, how far from the top-level node is it), it also needs to know the position of every parent node in the tree, so it knows whether to draw the pipe.

For example, consider the Validate-Zip-Files node in the desired output diagram above:

    │  │  └─Validate-Zip-Files

In order to print the correct sequence of pipes and spaces (space, pipe, pipe), it needs to know that Package is a "last child", while Zip-Files and Generate-Hashes are not.

All of my initial attempts involved passing in knowledge about the previous nodes, something like the following for example (though even this isn't sufficient):

void PrintNodeIncorrectly(Node node, int depth, bool isFirstChild, bool isLastChild, bool parentIsLastChild)
{
    // implementation
}

or passing in the parent nodes, so the child can calculate its indent

void PrintNodeButMakeHardWorkOfIt(Node node, bool isFirstChild, bool isLastChild, Node[] parentNodes)
{
    // implementation
}

Although that latter approach works, it's not very efficient, and feels wrong.

The aha moment for me was realising the "tell don't ask" principle applies here. Previously, I was trying to provide enough details about the parents of a node to calculate what its indent should look like. Instead, the key was for the parent to calculate what a child's indent should be, and pass that down directly.

Drawing the tree by pre-calculating the indent

With this in mind, I came up with the following small program which prints an ASCII tree (obtained from the function CreateNodeList). Rather than break this down afterwards, I've commented the code itself to explain what's going on:

class Program
{
    // Constants for drawing lines and spaces
    private const string _cross = " ├─";
    private const string _corner = " └─";
    private const string _vertical = " │ ";
    private const string _space = "   ";

    public static void Main(string[] args)
    {
        // Get the list of nodes from somewhere (not shown)
        List<Node> topLevelNodes = CreateNodeList();

        foreach (var node in topLevelNodes)
        {
            // Print the top level nodes. We start with an empty indent.
            // Also, all "top nodes" are effectively the "last child" in
            // their respective sub-trees
            PrintNode(node, indent: "", isLast: true);
        }
    }

    private static void PrintNode(Node node, string indent, bool isLast)
    {
        // Print the provided pipes/spaces indent
        Console.Write(indent);

        // Depending if this node is a last child, print the
        // corner or cross, and calculate the indent that will
        // be passed to its children
        if (isLast)
        {
            Console.Write(_corner);
            indent += _space;
        }
        else
        {
            Console.Write(_cross);
            indent += _vertical;
        }

        Console.WriteLine(node.Name);

        // Loop through the children recursively, passing in the
        // indent, and the isLast parameter
        var numberOfChildren = node.Children.Count;
        for (var i = 0; i < numberOfChildren; i++)
        {
            var child = node.Children[i];
            var isLast = (i == (numberOfChildren - 1));
            PrintNode(child, indent, isLast);
        }
    }

    private static List<Node> CreateNodeList()
    {
        // Load/Create the nodes from somewhere
    }
}

This function gets very close to the desired output with one very small flaw - it draws a corner prefix on all of the top-level/root nodes:

└─Default
   └─Package
      ├─Zip-Files
      │  ├─Generate-Hashes
      │  │  └─Validate-Zip-Files
      │  └─Copy-Files
      │     └─Run-Unit-Tests
      └─Create-Nuget-Packages
         └─Build
            └─Restore-Nuget-Packages

The extra └─ prefix on the top-level Default node is undesirable. There's a couple of ways to fix it.

Add an extra bool isTopLevelNode to the PrintNode() function
Use a different function when printing the top level nodes

I've chosen to go with the latter in the final code, shown below.

Drawing the tree with the correct top-level node prefix

The code below is the complete solution for printing the example I showed earlier. I've omitted the CreateNodeList() function as it's rather verbose. You can see a complete example on GitHub. Alternatively, see the original PR that inspired this post.

Compared to the solution in the previous section, this solution extracts the PrintChildNode() method from PrintNode. This allows us to only print the indent and cross/corner for child nodes, without having to pass additional parameters (e.g. isTopLevelNode) around.

class Program
{
    // Constants for drawing lines and spaces
    private const string _cross = " ├─";
    private const string _corner = " └─";
    private const string _vertical = " │ ";
    private const string _space = "   ";

    static void Main(string[] args)
    {
        // Get the list of nodes
        List<Node> topLevelNodes = CreateNodeList();

        foreach (var node in topLevelNodes)
        { 
            PrintNode(node, indent: "");
        }
    }

    static void PrintNode(Node node, string indent)
    {
        Console.WriteLine(node.Name);

        // Loop through the children recursively, passing in the
        // indent, and the isLast parameter
        var numberOfChildren = node.Children.Count;
        for (var i = 0; i < numberOfChildren; i++)
        {
            var child = node.Children[i];
            var isLast = (i == (numberOfChildren - 1));
            PrintChildNode(child, indent, isLast);
        }
    }

    static void PrintChildNode(Node node, string indent, bool isLast)
    {
        // Print the provided pipes/spaces indent
        Console.Write(indent);

        // Depending if this node is a last child, print the
        // corner or cross, and calculate the indent that will
        // be passed to its children
        if (isLast)
        {
            Console.Write(_corner);
            indent += _space;
        }
        else
        {
            Console.Write(_cross);
            indent += _vertical;
        }

        PrintNode(node, indent);
    }
    
    private static List<Node> CreateNodeList()
    {
        // Load/Create the nodes from somewhere
    }
}

Now the tree is printed just as we would like:

Default
 └─Package
    ├─Zip-Files
    │  ├─Generate-Hashes
    │  │  └─Validate-Zip-Files
    │  └─Copy-Files
    │     └─Run-Unit-Tests
    └─Create-Nuget-Packages
       └─Build
          └─Restore-Nuget-Packages

In these examples I have the corner/cross pieces descending from the second character of the parent node. Depending on how horizontally compact you'd like your tree to look, it's easy to tweak the various indent constants by adding additional space characters.

Summary

In this post I described the requirements for drawing an ASCII-art tree using C#. I highlighted the fact that each node appears to need to know about the status of all its parent nodes - a fact that makes the initial solution non-obvious. I then showed a solution that calculates a child node's indent in the parent node, and explicitly passes the indent as a method parameter to the child.

You can find the code for this post on GitHub. You can also find the PR I made to the Cake project, in which I make use of this approach to build a tree view of the tasks in a Cake build file. You can also see Immo Landwerth recreate a similar tree in his recent video on building a compiler, which I highly recommend watching.

Andrew Lock | .NET Escapades Andrew Lock