Getting the last child in a self-referencing hierachical tree

Question

I have the following type:

public class Category
{
    public string Id { get; set; }
    public string ParentId { get; set; }
    public string Title { get; set; }
}

Top level categories have a ParentId value of 0. Any child categories are related to their respective parent via the ParentId property.

I'm trying to implement a nice way of determining which is the last child in the tree (however deep that tree is), so in the following example, I would expect to have the 'Laptops' entry returned (or its Id at least):

Id: 10 ParentId: 0 Title: For Sale

Id: 5 ParentId: 10 Title: Computers

Id: 20 ParentId: 5 Title: Laptops

i.e. The hierachy being 'For Sale' > 'Computers' > 'Laptops'.

This hierachy may only consist of 1 Category OR it may in some cases have 5+ children.

Answer 1

Using LINQ, you can achieve this simply like this:

var LeafNodes = YourItemsList.Where(x => !YourItemsList.Any(y => y.ParentID == x.Id));

Now you can iterate over this enumerable and for each item, you can walk up the parent nodes to get the full chain.