Processing nested lists of items without recursion

axel g 0
Viewed 58

I have a class Item that looks as follows:

public class Item
{
   public string Name { get; set; }
   public int Value { get; set; }
   public List<Item> SubItems { get; set; }
}

Items can be nested over n levels, meaning that any item can contain a list of items of which each contains a list of items ...

I want to write a method that accepts an instance of item as an argument and returns the sum of value of all nested items.

My current recursive approach looks as follows:

public int GetSumOfValue(Item item)
{
   int sum = item.Value;
   if (item.SubItems == null)
   {
      return sum;
   }

   foreach (var subItem in item.SubItems)
   {
      sum += GetSumOfValue(subItem);
   }
   return sum;
}

While this works, I read that an iterative approach using a loop would be faster in most cases.

(Please note that I abstracted and shortened this method for the sake of brevity. This is not production code.)

I have a hard time figuring out how to turn my recursive approach into an iterative one since there are nested classes.

Any hints are appreciated. Thanks.

iteration recursion c#
2 Answers

You could use a Queue<Item> to collect all items:

public static int GetSumOfValue(Item item)
{
    if(item == null) 
    {
        throw new ArgumentNullException(nameof(item), "item must not be null");
    }

    int totalSum = 0;
    Queue<Item> queue = new Queue<Item>();
    queue.Enqueue(item);

    while (queue.Count > 0)
    {
        Item current = queue.Dequeue();
        totalSum += current.Value;
        foreach (Item subItem in current?.SubItems ?? Enumerable.Empty<Item>())
        {
            queue.Enqueue(subItem);
        }
    }

    return totalSum;
}
Tim Schmelter0

Here's a possible solution using Linq:

//test case 1
List<Item> items = new List<Item> 
{ 
    new Item { Name = "a", Value = 1, SubItems = new List<Item> { new Item { Name = "b", Value = 2, SubItems = new List<Item> { new Item { Name = "c", Value = 3, SubItems = null } } } } } 
};

//test case 2
List<Item> items2 = new List<Item> 
{ 
    new Item { Name = "a", Value = 1, SubItems = new List<Item> { new Item { Name = "b", Value = 2, SubItems = new List<Item> { new Item { Name = "c", Value = 3, SubItems = null } } } } },
    new Item { Name = "a", Value = 0, SubItems = new List<Item> { new Item { Name = "b", Value = 0, SubItems = new List<Item> { new Item { Name = "c", Value = 1, SubItems = null } } } } },
    new Item { Name = "a", Value = 0, SubItems = new List<Item> { new Item { Name = "b", Value = 0, SubItems = new List<Item> { new Item { Name = "c", Value = 1, SubItems = new List<Item> { new Item { Name = "c", Value = 1, SubItems = null } } } } } } } 
};

//test case 3
Item item = new Item { Name = "a", Value = 1, SubItems = new List<Item> { new Item { Name = "b", Value = 2, SubItems = new List<Item> { new Item { Name = "c", Value = 3, SubItems = null } } } } };
        
Console.WriteLine(SumItems(items)); //prints 6
Console.WriteLine(SumItems(items2)); //prints 9
Console.WriteLine(SumItem(item)); //prints 6

public class Item
{
   public string Name { get; set; }
   public int Value { get; set; }
   public List<Item> SubItems { get; set; }
}

//Just pass your singular item as a list with your top level item
//or I provided another implementation below that takes a single Item
public int SumItems(List<Item> items)
{
    int total = 0;
    while(true)
    {
        if(items == null || items.Count < 1)
            break;
        //sum the current level
        total += items.Sum(b => b.Value);
        //get a flat list of siblings
        items = items.SelectMany(a => a.SubItems ?? new List<Item>()).ToList() ?? new List<Item>();         
    }
    return total;
}

//singular method
public int SumItem(Item item)
{
    int total = 0;
    if(item == null)
       return total;

    if(item.SubItems == null || item.SubItems.Count < 1)
       return item.Value;
    
    total += item.Value;
    total += SumItems(item.SubItems);

    return total;
}
Ryan Wilson0
Related