Creating and working with a custom tree data structure in C#

This post is part of series:

Part 4 – Strongly typed SharePoint list operations using the repository pattern in F#
Part 3 – Bringing together repository and tree structure in business layer
Part 2 – Creating and working with a custom tree data structure in C#
Part 1 – Strongly typed SharePoint list operations using the repository pattern

I'd claim the tree data structure is underused in general application development. Sure, XML or tree view control APIs are generally tree-based underneath, but how often does an application use a tree structure in its business layer? Maybe it's because trees are initially a little hard to grasp given their recursive nature or maybe it's because we as developers are conditioned to approach problems from a more imperative angle.

It wasn't until recently, when I had to transform a tabular data structure into a tree data structure, that I created my own tree in C#. Here's the code I ended up with for constructing a tree, doing a depth-first search for a node, and printing the tree:

public class Tree<T> {
    public T Value;
    public IList<Tree<T>> Children;

    public Tree(T value) {
        Value = value;
        Children = new List<Tree<T>>();
    }

    public Tree<T> Find(Func<T, bool> predicate) {
        if (predicate(Value))
            return this;
           
        return Children
            .Select(c => c.Find(predicate))
            .FirstOrDefault(c => c != null);
    }

    public override string ToString() {
        return ToStringRecursive(this, 0);
    }

    private string ToStringRecursive(Tree<T> tree, int indentation) {
        var seed = (new String(' ', indentation)) + tree.Value + Environment.NewLine;
        return tree
            .Children
            .Aggregate(seed, (current, next) => current + 
                ToStringRecursive(next, indentation + 2));
    }
}

Constructing a tree of strings is done as follows:

var root = new Tree<string>("root") {
    Children = new List<Tree<string>> {
        new Tree<string>("node-1") {
            Children = new List<Tree<string>> {
                new Tree<string>("node-1.1") {
                    Children = new List<Tree<string>> {
                        new Tree<string>("node-1.1.1")  
                    }
                },
                new Tree<string>("node-1.2")
            }
        },
        new Tree<string>("node-2")
    }
};

Now you can query on the properties of the type of tree node:

System.Console.WriteLine(root);
/*
root
  node-1
    node-1.1
      node-1.1.1
    node-1.2
  node-2
*/

var node1 = root.Find(n => n == "node-1");
var node2 = node1.Find(n => n == "node-1.1.1");

System.Console.WriteLine(node1);
/*
node-1
  node-1.1
    node-1.1.1
  node-1.2
*/

System.Console.WriteLine(node2);
/*
node-1.1.1            
*/

Strictly speaking, the traversal logic doesn't belong to the tree class itself, but in a separate visitor class. Maybe at a later point, you want to add different traversal algorithms or some other code needs to iterate the tree to transform it. The visitor algorithms could be reused, calling out to a delegate for the details of the traversal.