Simplest way to Recurse Over Object Tree

Question

I have a base class:

public abstract class BaseClass{ 
    public bool IsSelected {get; set;}   
}

A derived class with a collection representing a hierarchy:

public class DerivedOne : BaseClass{
    public ObservableCollection<BaseClass> Children {get; set;}
}

Another derived class:

public class DerivedTwo : BaseClass{

}

What is the simplest way to find all of the elements under a DerivedOne root that have IsSelected set to true?

score 1 · Answer 1 · edited May 23 '17 at 11:45

You left out some requirement detail, but I think something like this should work:

public IEnumerable<BaseClass> AllIsSelected(BaseClass root)
{
    if (root.IsSelected)
    {
        yield return root;
    }
    var composite = root as DerivedOne;
    if (composite != null)
    {
        foreach (var v in composite.Children)
        {
            foreach (var x in AllIsSelected(v))
            {
                yield return x;
            }
        }
    }
}

Of course, if you want a full list all at once, you could build the list instead of using 'yield'.

This is the same design discussed here: IEnumerable and Recursion using yield return.

As another answer said, you can use LINQ to shorten this somewhat. This version avoids making the temporary list.

public IEnumerable<BaseClass> AllIsSelected(BaseClass root)
    {
        if (root.IsSelected)
        {
            yield return root;
        }
        var composite = root as DerivedOne;
        if (composite != null)
        {
            foreach (var x in composite.Children.SelectMany(v => AllIsSelected(v)))
            {
                yield return x;
            }
        }
    }

If one of the children is a DerivedOne too, this approach will ignore its children. As far as I understand the question, those should be traversed as well. I guess you need either some sort of stack or recursion. — timcbaoth, Mar 25 '16 at 23:53
@timcbaoth Thanks, I edited the code to iterate the children correctly. — Dave Tillman, Mar 26 '16 at 00:38

timcbaoth · Answer 2 · 2016-03-25T23:47:13.963

The simplest method would be to use LINQ with recursion

public IEnumerable<BaseClass> GetAllSelectedChildren(DerivedOne derivedOne)
{
    return derivedOne.Children.SelectMany(GetAllSelected);
}

public IEnumerable<BaseClass> GetAllSelected(BaseClass baseClass)
{
    var selected = new List<BaseClass>();

    if(baseClass.IsSelected)
    {
        selected.Add(baseClass);
    }

    var derivedOne = baseClass as DerivedOne;
    if(derivedOne != null)
    {
        selected.AddRange(GetAllSelectedChildren(derivedOne));
    }

    return selected;
}

score 0 · Answer 3 · answered Mar 26 '16 at 02:09

0

Use simple Linq.

  return root.Children
             .SelectMany(c => new[]{ c }.Concat(c.Children)) // flatten the structure including self node.
             .Where(e => e.IsSelected) // filter selected items
             .ToList();

answered Mar 26 '16 at 02:09

Hari Prasad

16,716
4
21
35

Will this scan the tree arbitrarily deep? I think it will only go one additional level. It also requires that **root** be a **DerivedOne** (which actually was a restriction stated in the requirements). The more general case is where **root** can be any **BaseClass**. – Dave Tillman Mar 26 '16 at 11:28

Simplest way to Recurse Over Object Tree

3 Answers3