Linq query for selecting an item from tree structure, but to look in the whole depth

Question

Here's a class I made:

public class ItemTree
{

    public Int32 id { get; set; }

    [JsonProperty(NullValueHandling = NullValueHandling.Ignore)]
    public String text { get; set; }

    [JsonProperty(NullValueHandling = NullValueHandling.Ignore)]
    public List<ItemTree> item { get; set; }

    public int parentId { get; set; }

}

And here's how I use it:

var tree = new ItemTree();
tree.id = 0;
tree.text = "sometext";
tree.item = new List<ItemTree>();

foreach (...)
{
    if (tree.item.Count == 0)
    {
      tree.item.Add(new ItemTree
      {
        id = my_id,
        text = my_name,
        item = new List<ItemTree>(),
        parentId = my_par
      });
    }
    else
    {
      tree.item.Where(x => x.id == my_par)
               .Select(x => x.item)
               .First()
               .Add(new ItemTree 
               {
                 id = my_id,
                 text = my_name,
                 item = new List<ItemTree>(),
                 parentId = my_par
               });
    }
}

And it crashes in the line with the Where clause. the reason it crashes is this: the tree has one item who has a list of items, and my query only checks the first item of the tree, not his children.

How to search in the whole depth of the tree and add an item there?

Answer 1

It might be convenient to flatten your tree structure into a list. Some logic will be easier to express if you just have an IEnumerable<ItemTree> that contains all the nodes of your tree. You're not losing any information, since you still have the parent ID on every node.

This is a naturally recursive problem. Using a recursive lambda, try something like:

Func<ItemTree, IEnumerable<ItemTree>> flattener = null;
flattener = t => new[] { t }
                .Concat(t.item == null 
                        ? Enumerable.Empty<ItemTree>()
                        : t.item.SelectMany(child => flattener(child)));

Note that when you make a recursive Func like this, you must declare the Func separately first, and set it to null.

You could also flatten the list using an iterator-block method:

public static IEnumerable<ItemTree> Flatten(ItemTree node)
{
    yield return node;
    if (node.item != null)
    {
         foreach(var child in node.item)
             foreach(var descendant in Flatten(child))
                 yield return descendant;
    }
}

Either way, once the tree is flattened you can do simple Linq queries over the flattened list to find nodes:

flattener(tree).Where(t => t.id == my_id);

Then, in order to add to the tree, you can do:

var itemOfInterest = flattenedTree.Where(t => t.id == myId).Single();
itemOfInterest.item = itemOfInterest.item ?? new List<ItemTree>();
itemOfInterest.item.Add(myItemToAdd);

Where flattenedTree was generated using one of our two flattening strategies.

I also want to note that item is not a great name for a property that is a list. Such properties are most often pluralized (items). Also, properties are usually capitalized (Items).

Answer 2

This might help:

public static IEnumerable<T> SelectRecursively<T>(this IEnumerable<T> e,
    Func<T, IEnumerable<T>> memberSelector)
{
    foreach (T item in e)
    {
        yield return item;

        IEnumerable<T> inner = memberSelector(item);

        if (inner != null)
            inner.SelectRecursively(memberSelector);
    }
}

With usage like:

List<ItemTree> tree = GetTree();
List<ItemTree> flattenedTree = tree.SelectRecursively(T => T.Items).ToList();

This will start recursive selection (deep traversal), where you can use other LinQ features, like .Where().