How to get all subobjects from a CustomObject with n Children/Subchildren and so on

Question

I have a CustomObject with n Children. These children are a List of CustomObjects. Something like this:

public class CustomObject
{
    public List<CustomObject> Children = new List<CustomObject>();
}

What I am looking for is the most performant way to get ALL n Children and their children and subchildren etc, from a single instance of CustomObject. Is there a better way than looping through all veigns until I reach the end (null)?

(C#, .NET 3.5)

To make it more clear, I will make an example structure:

//root object
CustomObject.Children ->
    CustomObject.Children ->
         CustomObject
         CustomObject
    CustomObject.Children ->
         CustomObject.Children ->
             CustomObject
         CustomObject
    CustomObject

In this case, I need to get ALL custom objects beneath the root object.

I don't see anything wrong with a loop and recursion for this instance. There might be some fancy LINQ that can be applied that someone may contribute, but other than that a simple loop and recursion seems perfectly apt to me. — Lloyd Powell, Dec 12 '11 at 14:46

score 7 · Accepted Answer · answered Dec 12 '11 at 14:47

No, you just have to loop through everything. You can use a recursive method:

public void GetItems(List<CustomObject> list) {
  list.Add(this);
  foreach (CustomObject child in Childs) {
    child.GetItems(list);
  }
}

Usage:

List<CustomObject> items = new List<CustomObject>();
someCustomObject.GetItems(items);

Note: The plural form of child is children.

Sebastian Piu · Answer 2 · 2011-12-12T15:07:14.363

4

I use this Extension method:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> hierarchy, Func<T, IEnumerable<T>> lambda)
    {
        var result = new List<T>();

        foreach (var item in hierarchy)
        {
            result.AddRange(Flatten(lambda(item), lambda));
            if (!result.Contains(item))
                result.Add(item);
        }

        return result;
    }

you will call it like this:

MyObject.Childs.Flatten(c => c.Childs);

here is a rather ugly override that adds the root object if wanted:

public static IEnumerable<T> Flatten<T>(this T @this, Func<T, IEnumerable<T>> lambda)
{
    return new[] { @this }.Flatten(lambda);
}

edited Dec 12 '11 at 15:07

answered Dec 12 '11 at 14:48

Sebastian Piu

7,838
1
32
50

I like this solution, but it should be callable on a T, add that T, and does not need to be checking if each item is contained already. If the goal was to have only one instance of each type, then a Set should be used instead. – Chris Pitman Dec 12 '11 at 15:00
I think I have an ugly override to add the root T if neccesary that it adds it to a list and then calls flatten in it. Good point on the Set, I guess it could use a HashSet instead of the list – Sebastian Piu Dec 12 '11 at 15:04

Andras Zoltan · Answer 3 · 2011-12-12T14:53:47.003

2

Probably not, but it does depend entirely on how you've done it. You could use yield recursively:

public IEnumerable<CustomObject> AndChildren()
{
  yield return this;
  foreach(var child in Childs)
  {
    foreach(var nested in child.AndChildren())
    {
      yield return nested;
    }
  }
}

Which has the obvious benefit that it's late-bound and therefore much better on your memory consumption. The downside is that it's extremely fragile in terms of any modifications being made to any node within the tree (the foreach iterators will raise an exception on next if any of the lists are modified).

To get around that you can eager-load the result using the Linq .ToArray() method.

So now, if you want to iterate through an entire tree you simply do:

foreach(var obj in the_root_object.AndChildren())
{

}

Assuming the_root_object is an instance of CustomObject that has various 'veins', as you've put it.

This would have to be rewritten slightly if you have a specific requirement on the order that objects should appear relative to their children.

edited Dec 12 '11 at 14:53

answered Dec 12 '11 at 14:47

Andras Zoltan

41,961
13
104
160

Beware of nested yields, http://stackoverflow.com/questions/1043050/c-sharp-performance-of-nested-yield-in-a-tree – Chris Pitman Dec 12 '11 at 14:56
@Chris - agreed, if we have a big, deep, tree then there could issues in which case eager flattening, probably via a single-stack-based solution would be much better. – Andras Zoltan Dec 12 '11 at 15:00
@Chris - that said, however, I can't see how this is not as good as the Flatten solution posted by Sebastian - they're ostensibly identical (except for the fact I didn't write it as an extension, easily done) - with mine doing the same thing if you use `ToArray`. Any recursive solution will have the same issue, regardless of whether yield is used or not. – Andras Zoltan Dec 12 '11 at 15:10
It is not that the solution is recursive, it is the use of recursive autogenerated enumerables. There is significant overhead on 1) keeping the state and 2) descending through every enumerable for each iteration. Iteration of a tree can easily become O(nlgn) instead of lg(n). The other solutions build a list as they recurse, trading O(n) runtime of O(n) space. A custom written iterator would be able to get O(n) runtime and also O(1) space, which is probably the best yet most complex answer. – Chris Pitman Dec 12 '11 at 18:33

score 2 · Answer 4 · answered Dec 12 '11 at 14:49

You would have to iterate over each of the Childs collection. You may consider something like this however:

public class CustomObject
{
    public List<CustomObject> Childs = new List<CustomObject>();

    protected IEnumerable<CustomObject> GetDecendants()
    {
        foreach (var child in Childs)
        {
            yield return child;
            foreach (var grandchild in child.GetDecendants())
            {
                yield return grandchild;
            }
        }
    }
}

score 1 · Answer 5 · answered Dec 12 '11 at 14:48

1

I would just use a loop and recursion, can't get much simpler!

private List<CustomObject> GetChildObjects(CustomObject)
{
   List<CustomObject> retList = CustomObject.Childs;

   foreach(CustomerObject obj in retList)
   {
      retList.AddRange(GetChildObjects(obj));
   }

   return retList;
}

answered Dec 12 '11 at 14:48

Lloyd Powell

18,270
17
87
123

This would give a exception as the item being enumerated is changed – Rajshekar Reddy Mar 25 '15 at 12:41

score 0 · Answer 6 · answered Dec 12 '11 at 17:37

If you aren't interested in maintaining the hierarchy of these objects, but are only after obtaining all of them (I could not make out from your post if you are), you could also consider using Reflection to obtain all objects of type CustomObject:

List<CustomObject> Objects = new List<CustomObject>();

Assembly asm = Assembly.LoadFrom(assemblyPath);
Type[] types = asm.GetTypes();

foreach (var t in types)
{
    if (t.IsClass && t.IsSubclassOf(typeof(CustomObject)))
    {
        var instance = (CustomObject) Activator.CreateObject(t);

        if (!Objects.Contains(instance))
            Objects.Add(instance);
    }
}

Especially in larger applications, running a large amount of loops can have a huge impact on performance, and using Reflection generally is a good alternative.

How to get all subobjects from a CustomObject with n Children/Subchildren and so on

6 Answers6