Linq query for selecting an item from tree structu

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

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().

Answer 2

Solution of @AgentFire from 2013-06-13 at 12:14 must extended to

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)
        {
            foreach(T innerItem in inner.SelectRecursively(memberSelector))
            {
                yield return innerItem;
            }
        }
    }
}

to get the inner items into your result list.

Thanks @AgentFire for this nice idea.

Answer 3

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 4

You are using First() instead of FirstOrDefault(). You should do something like the following instead.

var item = tree.item.Where(x => x.id == my_par)
           .Select(x => x.item)
           .FirstOrDefault();

if (item != null)
           .Add(new ItemTree 
           {
             id = my_id,
             text = my_name,
             item = new List<ItemTree>(),
             parentId = my_par
           });

Answer 5

You will need to recurse the tree somehow. One solution is to make an iterator for the ItemTree object, something like:

public class ItemTree
{
  //simple DFS walk of the tree
  public IEnumerable<ItemTree> GetChildren()
  {
     //no items, stop execution
     if ((item == null) || (item.Count == 0))
       yield break;
     foreach (var child in item)
     {
        //return the child first
        yield return child;
        //no way to yield return a collection
        foreach (var grandchild in child.GetChildren())
        {
           yield return grandchild;
        }
     }
  }
}

Now locating the parent is trivial, something like

var parent = tree.GetChilden().First(c => c.id == my_par);
parent.Add(new ItemTree 
{
  id = my_id,
  text = my_name,
  item = new List<ItemTree>(),
  parentId = my_par
});

Answer 6

1. You should add a mehod HasId in your ItemTree
2. The method should implement a recursive search of particulat Id and return answer true or false
3. use (x => x.HasId(my_par))