Hierarchy Problem -> Replace Recursion with Linq Join?

Question

I have a self referential table, which has ID, ParentID (nullable).

So, the table contains many nodes, each node could be the root in the hierarchy (parent is null), or any level of the hierarchy (parent exists elsewhere in the table).

Given an arbitrary starting node, is there an elegant linq query that will return all children of the hierarchy from that node?

Thanks.

Answer 1

If you want to select all direct children of a node, a simple query like the following should do the job:

from item in table
where item.ID == parentID;
select item

If you want to select all descendants of a node, this is not possible with LINQ, because it requires recursion or a stack which LINQ (and SQL) doesn't provide.

See also:

• StackOverflow: LINQ to SQL for self-referencing tables?
• CodeProject: T-SQL - How to get all descendants of a given element in a hierarchical table
• StackOverflow: Expressing recursion in LINQ

Answer 2

Here is a quick one I just wrote:

class MyTable
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
    public MyTable(int id, int? parentId) { this.Id = id; this.ParentId = parentId; }
}

List<MyTable> allTables = new List<MyTable> {
    new MyTable(0, null), 
    new MyTable(1, 0),
    new MyTable(2, 1)
};

Func<int, IEnumerable<MyTable>> f = null;
f = (id) =>
{
    IEnumerable<MyTable> table = allTables.Where(t => t.Id == id);

    if (allTables
        .Where(t => t.ParentId.HasValue && t.ParentId.Value == table
            .First().Id).Count() != 0)
        return table
            .Union(f(
            allTables.Where(t => t.ParentId.HasValue && t.ParentId.Value == table
                .First().Id).First().Id));
    else return table;

};

But I believe it is possible to do using SQL with a Union ALL.

Answer 3

I know this is an old post but you should check out this extension:

http://www.scip.be/index.php?Page=ArticlesNET23

I've been using it and it is working great.

Answer 4

Basically I'm going with something like this as discussed in the SO link you proivded.

public IQueryable GetCategories(Category parent)
{
    var cats = (parent.Categories);
    foreach (Category c in cats )
    {
        cats  = cats .Concat(GetCategories(c));
    }
    return a;
}

CTEs are probably the best solution but I'd like to keep things all in the same tier for now.