Get a collection of child positions for a given parent position

Question

I am trying to get a complete tree in a single loop using an iterative function. For instance, this is what I have:

var someVariable = GetAllChildPositions(posId) //Method called from a console method.



public ICollection<Position> GetAllChildPositions(int posId)
{
    ICollection<Position> posCollection = new Collection<Position>();
    posCollection= GetChildPos(posId,posCollection);
    return posCollection;
}

public ICollection<Position> GetChildPos(int posId, ICollection<Position> posCollection) 
{
    var posObject= serviceRepo.Position.GetById(posId);
    posCollection.Add(posObject);
    if (serviceRepo.Position.GetAll().Where(x => x.ParentPosId == posId).Any())
    {
        var childPositions = serviceRepo.Position().GetAll().Where(x => x.ParentPosId == posId);
        foreach (var childPos in childPositions )
        {
            GetChildRows(childPos.Id, posCollection);
        }
    }
    return posCollection;
}

I am trying to get a list/collection child positions for a given parent position Id. This method works quite well and gets the job done albeit a little slowly. I am interested in knowing if there is a better way of doing this.

Answer 1

If Position and Position() in your code is the same and you supposed to call GetChildPos instead of GetChildRows in the inner loop then your code can be significantly simplified:

var someVariable = GetChildPos(posId).ToList();

public IEnumerable<Position> GetChildPos(int posId)
{
    yield return serviceRepo.Position.GetById(posId);

    foreach (var pos in serviceRepo.Position().GetAll()
                                              .Where(x => x.ParentPosId == posId)
                                              .SelectMany(x => GetChildPos(x.Id)))
    {
        yield return pos;
    }
}

Also it can improve performance because in your original code you do this instructions

serviceRepo.Position().GetAll().Where(x => x.ParentPosId == posId)

two times that can cause slowing down if some method in this chain is not lazy and executes heavy code even for Any().

Answer 2

I think @Maxim's answer should yield a reasonable improvement and as mentioned in the comment you could pass in the Position object directly saving a call to GetById every single time.

One consideration not mentioned: If GetAll actually returns all Positions in a non-lazy fashion then you'd be better off putting the Positions into a Dictionary<int, Position> keyed by their id and performing the search in a single loop by either using a stack or a queue (depth first vs breadth first)

Answer 3

What really would speed this up would be to store the result of serviceRepo.Position().GetAll() into a variable and pass this as an argument to the desired method. In its current state you query for the "root" item at least one time(.Any()) but only if there aren't any children.

If there are children, you make this call a second time and for each child you do at least one more call.
So for a tree like this

      A
     / \
    B   C
   / \
  D   E
     / \
    F   G

This call would happen 10 times.

---

If we would integrate this into @Maxim's answer we would get

public IEnumerable<Position> GetChildPos(int posId)
{
    var positions = serviceRepo.Position().GetAll()
    return GetChildPos(posId, positions);
}  

public IEnumerable<Position> GetChildPos(int posId, IEnumerable<SomeObject> positions)
{
    yield return serviceRepo.Position.GetById(posId);

    foreach (var pos in positions.Where(x => x.ParentPosId == posId)
                                 .SelectMany(x => GetChildPos(x.Id, positions)))
    {
        yield return pos;
    }
}