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?

@kostasch. Yes. tree.item.Where(x => x.id == my_par) is null and it throws nullPointerException. — petko_stankoski, Jun 13 '13 at 11:50
Can you explain what the line with the `Where` is supposed to be doing? It seems that it tries to insert a grandchild on the first child of the item in a roundabout way? — SWeko, Jun 13 '13 at 11:51
@SWeko it needs to insert a child in the tree. The parent of the child should be the item with id == my_par — petko_stankoski, Jun 13 '13 at 11:52
So the problem is, find a node in the tree and insert a child? — SWeko, Jun 13 '13 at 11:53
I suppose you have check that tree.item has ItemTree with id == my_par? Imean r you sure that your select have to bring values? — kostas ch., Jun 13 '13 at 11:56

Ben Reich · Answer 1 · 2013-06-13T13:07:44.487

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

+1. Note: since this is a recursively defined lambda, the declaration line is mandatory. `Func<...> flattener = ...` would not work — SWeko, Jun 13 '13 at 12:05
I have answered this too. But your answered remembered me the recursive lambdas! So +1! — Kaveh Shahbazian, Jun 13 '13 at 12:10
And how would I add the new ItemTree object to this? The one that's in the foreach loop, in the else. — petko_stankoski, Jun 13 '13 at 12:15
@petko_stankoski See my updated answer regarding adding nodes to the tree — Ben Reich, Jun 13 '13 at 13:31

AgentFire · Answer 2 · 2013-06-15T18:35:13.570

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

edited Jun 15 '13 at 18:35

answered Jun 13 '13 at 12:14

AgentFire

8,944
8
43
90

And how would I add the new ItemTree object to this? The one that's in the foreach loop, in the else. – petko_stankoski Jun 13 '13 at 12:15
@petko_stankoski you just simply get an `ItemTree` and call the `.Items.Add(...)` method on the List. – AgentFire Jun 13 '13 at 12:17

VBWebProfi · Answer 3 · 2018-02-10T19:44:23.357

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.

score 0 · Answer 4 · answered Jun 13 '13 at 11:52

0

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
           });

answered Jun 13 '13 at 11:52

shamp00

11,106
4
38
81

You don't understand. There must be an item in the tree with id == my_par. The problem here is that I don't search in the whole tree. – petko_stankoski Jun 13 '13 at 11:54

score 0 · Answer 5 · answered Jun 13 '13 at 12:01

0

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

answered Jun 13 '13 at 12:01

Yaugen Vlasau

2,148
1
17
38

Isn't that what I wrote in the question? – petko_stankoski Jun 13 '13 at 12:02

SWeko · Answer 6 · 2013-06-13T12:50:35.193

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
});

Ok and how would I add the new ItemTree object to the one GetChildren returns? — petko_stankoski, Jun 13 '13 at 12:11
Edited the response to show the actual adding (it's a simple add operation) — SWeko, Jun 13 '13 at 12:51

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

6 Answers6

Linked