Finding a path of recursion

Question

Hello everyone I have a small problem and I feel a little bit stuck. I manage to get the object that I want, but I don't know how to return the path to that object (how I found it). My code looks like this at the moment:

P.S what I mean by path: every single item has it's name and id. I manage to find an object with id (which I give when call for recursion) and when I find it, I need to create string and add all of it's parents names to it and return it.

protected void FindPath(int depth, int id, InventLocationViewModel currentLocation)
    {
        if (depth < 0)
            return;

        if (currentLocation.Id == id)
        {
            selectedLocation = currentLocation;
            return;
        }

        foreach (var child in currentLocation.ChildInventLocations)
        {
            FindPath(depth - 1, id, child);
        }
    }

    protected void SelectedLocation(RecursiveSelectObject args)
    {
        currentLocation = locations.InventLocations.FirstOrDefault(e => e.Id == locationId.Value);

        FindPath(args.Level, args.Id, currentLocation);

        if (selectedLocation.Id == args.Id)
        {

        }
    }

Answer 1

You can avoid recursiveness and return the tree path of every node with this simple code

Something like this

public IEnumerable<InventLocationViewModel> GetPathToId(int findingId, int maxDepth, InventLocationViewModel rootLocation)
{
    if (rootLocation is null) throw new ArgumentNullException(nameof(rootLocation));
    if (findingId == rootLocation.Id) //same location
        return Enumerable.Repeat(rootLocation, 1);

    var stack = new Stack<(InventLocationViewModel, int)>(); //we use a tuple for keep the record of the depth
    var visitedPoints = new HashSet<InventLocationViewModel>() { rootLocation };

    stack.Push((rootLocation, 0)); //we put the root

    while (stack.TryPop(out var (currentSearchLocation, depth)))
    { //we take the bottom most recent object

        if (currentSearchLocation?.Id == findingId)
        {
            //this is the path from the root to the leaf WITHOUT THE LEAF
            //return stack.Select(tuple => tuple.Item1);
            
            //re-inject the currentSearchLocation if needed;
            stack.Push((currentSearchLocation, depth));
            return stack.Select(tuple => tuple.Item1);
        }
        if (depth >= maxDepth)
            continue;
        foreach (var inventLocation in currentSearchLocation.ChildLocations ?? Enumerable.Empty<InventLocationViewModel>()) //we
        {
            if (!visitedPoints.Contains(inventLocation))
            {
                visitedPoints.Add(inventLocation);
                stack.Push((inventLocation, depth+1));

            }
        }
    }
    return null; //not found;
}

Edit: there is one bug with tree depth check, I'm fixing it.

Edit3: max depth constraint fixed.

Answer 2

You know what you want to keep on the way out:

protected List<InventLocationViewModel> FindPath(int id, InventLocationViewModel currentLocation)
{
    if (currentLocation.Id == id)
    {
        return new List<InventLocationViewModel> {currentLocation};
    }

    foreach (var child in currentLocation.ChildInventLocations)
    {
        var result = FindPath(id, child);
        if (result != null)
        {
            result.Add(currentLocation);
            return result;
        }
    }
    return null;
}