Find value/item in class/object/list with multiple nested children

Question

I have this class:

public class Division
{
    public int Id { get; set; }
    public string Naam { get; set; }
    public ICollection<Division> Children { get; set; }
}

Example of the filled object/list:


Id  1
Name    "HQ"
Children    
   0    
   Id   200
   Name "HR"
   Children 
      0 
      Id    800
      Name  "Payrolls"
      Children  
         0  
         Id 1001
         Name   "Years"
         Children   
         1
         Id 1002
         Name   "Level"
         Children   
      1 
      Id    900
      Name  "Functions"
      Children  
         0  
         Id 2000
         Naam   "Grades"
         Children   
...

Each item can have many nested 'Children'. Now I want to find an item by Id, how can I achieve this?

I tried to put the result into a list. lstDivision = Division.Children.ToList();

and find the item by: Division d = lstDivision.SelectMany(d => d.Children).Where(c => c.Id==2000).FirstOrDefault();

The result is null.

The code you tried only traverses 2 Levels but your target ID is on Level 3 deep. — Fildor, Nov 29 '22 at 07:57
Depending on your requirements and knowledge, you can go for different recursive approaches but also iterative. OR you can choose to have a second datastructure, which would be a `Dictionary`, so you can look up item by ID fast (given that IDs are unique). — Fildor, Nov 29 '22 at 07:59
If you do not want to keep two datastructures up to date at all times, you could also go for a "cache" approach, where you would look for an ID in the dictionary, if not found perform tree search, then write to dictionary and return result, so the next query for the same ID is faster... just remeber to clear it from cache if it gets deleted. — Fildor, Nov 29 '22 at 08:05

score 1 · Answer 1 · answered Nov 29 '22 at 08:23

from https://stackoverflow.com/a/73486312/659190,

with,

public static IEnumerable<T> DepthFirstTraversal<T>(
    this T root,
    Func<T, IEnumerable<T>> branchSelector)
{
    ArgumentNullException.ThrowIfNull(branchSelector);
    
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        
        if (current == null)
        {
            continue;
        }
        
        foreach(var child in branchSelector(current))
        {
            stack.Push(child);
        }
    }
}

you can do,

division
   .DepthFirstTraversal(d => d.Children)
   .Where(c => c.Id==2000)
   .FirstOrDefault();

Fildor · Answer 2 · 2022-11-29T08:28:39.577

An example of a naive recursive approach would be this:

// given: `Division` is a nullable reference type, probably a class
// I am refering to the `Division` class as given in question at the time of writing.

public Division FindDivisionByID( Division parent, int targetID )
{
    // Do we have the Node we were looking for already?
    // Yes: Return it.
    if( parent.Id == targetId ) return parent;

    // No: Process Children one by one
    foreach( var child in parent.Children )
    // Little assignment for OP: ^^ this does not take into account
    // that `parent.Children` could be null and will throw if it is.
    // You would want to fortify against that.
    {
        // If a descendant of this child or the child itself
        // was the one we are looking for, `childResult` will 
        // point to it. If not it will be null.
        var childResult = FindDivisionByID( child, targetID );
        // The requested Node was in this child's subtree?
        // Yes: Return it.
        if( childResult is not null ) return childResult;
        // No: Next child if there is one.
    }
    // Neither this Node nor any of its Children nor any of their 
    // descendants was the one we are looking for.
    return null;
}

I'd recommend to additionally use a cache for faster lookups (given they happen frequently).

Note that this is only one way to achieve the goal. There are many different ways to traverse a tree. Some more, some less efficient. It's definitely worth it to dive into this, even if it is only to "have heard it once".

Find value/item in class/object/list with multiple nested children

2 Answers2

Linked