Query for terminal node in hierarchy RRS feed

  • Question

  •  I have a table with a self-referencing key that is represented below. Imagine categories that can themselves be divided into categories. Some Categories have sub-categories, some are bottom-level, with no sub-categories. The DB experts tell me this is called the adjacency model.

    What I want is to query for subcategories that have no related subcategories, ie, “terminal nodes.” In this case, want just "Angels" if I'm looking for the terminal nodes associated with "Living Things". I wouldn't want Animals and Plants because they have categories associated with them

    Id         Name                            ParentId (references Id)

    1          Living Things                 null
    2          Non-Living Things          null
    3          Animals                        1
    4          Plants                           1
    5          Angels                          1
    6          Rocks                           2
    7          Gases                           2
    8          Dogs                            3
    9          Cats                             3
    10         Trees                            4
    11         Grass                           4 

    If you wrote out the Hierarchy it would look like:

                Living Things
                Non-Living Things

    What I’m interest in is using Linq to find the red items within a given parent category (the terminal node, basically). In other words, Items that have no subcategories. If I was working with Living things, I want to find Angels by asking “give me all categories whose ParentId == 1, but whose Id is not found in any other entity’s ParentId column.

    The  easy part, I got:

                IList<Categories> subcategories = context.Where( c => c.ParentId == 1).ToList(); 

    But narrowing it to categories with no subcategories is turning me around. Any help would be much appreciated.

    Thanks for you help.

    Monday, January 5, 2009 10:24 PM


  • After hammering on it for a while, and making friends with LinqPad, this seemed to do the trick:

    Categories.Where( c => !c.Children.Any ( d => d.ParentId == c.Id)).Where( e => e.ParentId == 1) 

    • Marked as answer by j_lembke Tuesday, January 6, 2009 2:36 AM
    Tuesday, January 6, 2009 2:36 AM