0

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.

5
  • What are your speed / memory limitations? You can either use DFS or recursion Apr 16, 2015 at 15:48
  • Can you define last a bit more precisely? Is that the last child in any branch (since each branch can have multiple children), or the deepest child?
    – LiamK
    Apr 16, 2015 at 15:49
  • wait... do you have all the items in a list or just the root category?
    – Ewan
    Apr 16, 2015 at 15:56
  • I'm dealing with the same structure, but (argh!) in PHP/Javascript/MySql. I added a couple of useful parameters: "order of visualization" and "branch-id". Then I made IP-like dotted codes (they are unique) simply chaining all the "branch-id"s. In your case "1.5.20.3.12" could be "for sale - computer - laptop - IBM - Thinkpad", but it's easier to know how many 1.5.20 or 1.5.20.3 you have. Apr 16, 2015 at 15:58
  • 'in a self-referencing hierachical tree' ie do you mean a graph ( ie a can be a parent of b is a parent of c is a parent of a)? if so what does 'last' mean?
    – tolanj
    Apr 16, 2015 at 16:04

3 Answers 3

2

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.

3
  • This is doing a linear search of the list for every item in this list, which scales very poorly with the size of the collection.
    – Servy
    Apr 16, 2015 at 15:55
  • @Servy: Hmmm... OP said he can have upto 5+ items per category, so he's not missing much more than a few microseconds with it, I guess. For larger lists however your point is very valid.
    – dotNET
    Apr 16, 2015 at 15:57
  • Each category has up to 5 children. But if there are 1,000 categories that this operation is performed on...
    – Servy
    Apr 16, 2015 at 15:58
2

By creating a lookup with the parent Id as the key you can easily find all children for a given node, allowing you to easily find all nodes without any children.

var lookup = categories.ToLookup(category => category.ParentId);
var leaves = categories.Where(category => !lookup[category.Id].Any());
0

Using LINQ, you can achieve this simply like this:

var filteredData = parentChildData.Where(x => (parentChildData.All(y => y.ParentId != x.Id))).ToList();
1
  • Why do you preferred this over the existing answers? Mar 15 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.