Loading flat data into a tree data structure

Question

Currently, I have an Item class and a list of items representing flat data retrieved from a SQL Server 2012 DB query. Here is the Item class.

public class Item
{
    public string Parent { get; set; }
    public string Child { get; set; }
    public string Name { get; set; }
    public int Quantity { get; set; }
}

I need to transform this flat data into a tree structure and have the ability to traverse the tree while performing some action. Here is a visual of some data. My tree will always have a single root node.

I have seen several posts on SO pertaining to this but I'm still struggling with it. Here is the generic TreeNode class I have.

public class TreeNode<T>
{
    private readonly T _value;
    private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

    public TreeNode(T value)
    {
        _value = value;
    }

    public TreeNode<T> this[int i]
    {
        get { return _children[i]; }
    }

    public TreeNode<T> Parent { get; private set; }

    public T Value { get { return _value; } }

    public ReadOnlyCollection<TreeNode<T>> Children
    {
        get { return _children.AsReadOnly(); }
    }

    public TreeNode<T> AddChild(T value)
    {
        var node = new TreeNode<T>(value) { Parent = this };
        _children.Add(node);
        return node;
    }

    public TreeNode<T>[] AddChildren(params T[] values)
    {
        return values.Select(AddChild).ToArray();
    }

    public bool RemoveChild(TreeNode<T> node)
    {
        return _children.Remove(node);
    }

    public void Traverse(Action<T> action)
    {
        action(Value);
        foreach (var child in _children)
            child.Traverse(action);
    }

    public IEnumerable<T> Flatten()
    {
        return new[] { Value }.Concat(_children.SelectMany(x => x.Flatten()));
    }
}

I'm having trouble recursively loading the flat data into the tree structure. I also don't understand how to utilize the Action inside the Traverse method to perform some task while traversing. To populate the tree, I believe I need to start with the root. I obtain it like this:

var root = new TreeNode<Item>(items.Single(i => i.Parent == null));

I can then load the first level down like so:

root.AddChildren(items.Where(i => i.Parent.Equals(root.Value.Child)).ToArray());

My two questions are as follows:

1. How can I recursively load everything?
2. How do I use the Action inside the Traverse method to simply write out the tree structure by item names with proper indentation (or perform any task for that matter)?

Thanks in advance!!

Answer 1

First question: recursive loading

You need to create a helper function (if you code in C# 7.0 you can do that as a local function and strip the items parameter):

private static void AddDescendants(IReadOnlyCollection<Item> items, TreeNode<Item> node)
{
    var children = node.AddChildren(items.Where(i => i.Parent == node.Value.Child).ToArray());
    foreach (var child in children)
    {
        AddDescendants(items, child);
    }
}

Calling it, as per your example after obtaining root:

var root = new TreeNode<Item>(items.Single(i => i.Parent == null));
AddDescendants(items, root);

Second question: Traversal

Your Traverse function does pre-order traversal and provides absolutely no information whatsoever on which tree level you are, and so cannot be used to perform indentation in output.

If you change the implementation to take Action<TreeNode<T>> like so:

public void Traverse(Action<TreeNode<T>> action)
{
    action(this);
    foreach (var child in _children)
        child.Traverse(action);
}

Then you can calculate indentation level by counting parents:

root.Traverse(node =>
{
    var depth = 0;
    var ancestor = node.Parent;
    while (ancestor != null)
    {
        depth++;
        ancestor = ancestor.Parent;
    }
    Console.WriteLine(new string(' ', depth * 2) + node.Value.Name);
});

Here's a full working sample with output: https://ideone.com/faVOtd