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

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.

CodePudding user response：

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();

CodePudding user response：

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".