Linq to filter tree

Question

Class structure

public clas Item 
{
   public Item Parent { get; set; }

   public string Code { get; set; }
}

example tree

AAA
 - AAB
    - BBB
CCC
 - CCA

So i want to filter tree by CODE == BBB and result should be

AAA
 - AAB
    - BBB

but if i filter like this

IQueryable<Item> itemsQuery = GetQuery();
itemsQuery = itemsQuery.Where(x => x.Code == "BBB")

result does not contain parent nodes. So, how to include parent nodes, if their child nodes satisfy certain conditions?

You could try `itemsQuery.Where(x => x.Code == "BBB").Select(x => x.Parent)` or even use the `new` keyword if you want to create a structure (depending on your need). — Keyur PATEL, Feb 08 '17 at 07:43
Do you use Entity Framework? If you use EF you should `Include` The `Parent` Property. If not, is the Item initialized? What have you done so far? What does `GetQuery()` do? — Sebastian Siemens, Feb 08 '17 at 07:44
See http://stackoverflow.com/questions/11565423/most-efficient-method-of-self-referencing-tree-using-entity-framework — Ian Mercer, Feb 08 '17 at 07:49
Short answer is that you cannot. LINQ operates on linear `IEnumerable` sequences not tree structures. You either need to repeatedly hit the database to get the parent records OR you need to change the database structure to represent the hierarchy in a more accessible way. — Ian Mercer, Feb 08 '17 at 07:56

score 0 · Answer 1 · answered Feb 08 '17 at 08:21

In simple way, you cannot get recursive tree using EF. EF returns flat collections. However, there are workarounds.

Variant 1:

Add to your Item public Item Root { get; set; } and public ICollection<Item> AllSiblings { get; set; } property, which points all items to the actual root and second is the other way (all nested items).

The query than make look like:

IQueryable<Item> itemsQuery = GetQuery().Include(x => x.AllSiblings);
itemsQuery = itemsQuery.Where(x => x.Code == "BBB" || x.AllSiblings.Any(s => s.Code == "BBB")).ToList();

Now you have all items in your app and you can than recursively make the tree in C#.

Variant 2:

You can make several SQL queries to get each parent of found items. This is not recommended, because it will get very slow on more found results.

score 0 · Answer 2 · answered Feb 09 '17 at 08:26

It is hard to apply LinQ here since there is no reference from parent items to children. What about doing simple enumeration to parent after applying filter? It will give you list of all matched items in the tree and then you'll might need to print it in a "tree" manner. Here is a BFS example

        IQueryable<Item> itemsQuery = items.AsQueryable();
        itemsQuery = itemsQuery.Where(x => x.Code == "BBB");

        var bfsQueue = new Queue<Item>(itemsQuery);
        var matchedItemsSet = new HashSet<Item>();

        while (bfsQueue.Count > 0) {
            var item = bfsQueue.Dequeue();
            matchedItemsSet.Add(item);

            var parent = item.Parent;
            if (parent != null && !matchedItemsSet.Contains(parent))
            {
                bfsQueue.Enqueue(parent);
            }
        }

        foreach (var item in matchedItemsSet) {
            Console.WriteLine(item.Code);
        }

score 0 · Answer 3 · answered Feb 09 '17 at 09:32

I prefer universal approaches.

public static IEnumerable<T> SelectUntil<T>(this T element, Func<T, T> nextMemberSelector, Func<T, bool> stopCondition)
{
    while (!stopCondition(element))
    {
        yield return element;
        element = nextMemberSelector(element);
    }
}
public static IEnumerable<Item> GetAncestors(this Item e)
{
    // Or don't Skip(1) if you need the child itself included.
    return e.SelectUntil(T => T.Parent, T => T.Parent == null).Skip(1);
}

private static void Main(string[] args)
{
    IEnumerable<Item> itemsQuery = GetQuery();
    IEnumerable<Item> filter = itemsQuery.Where(T => T.Code == "BBB");

    foreach (Item item in filter)
    {
        Item[] allParents = item.GetAncestors().ToArray();
    }

}

Linq to filter tree

3 Answers3