CODEWITHSUNDEEP
c#linqtree
user3322417
user3322417

Reputation: 191

Retrieve a list of tree paths

I currently have a tree and i am using the code found here Functionally traversing a tree in C# to get the paths in my tree. The thing is, this code currently returns a list of each path in my tree. For example, if i have the following tree:

A---
    |
    ---B
    |
    ---C
       |
       ---D
       |
       ---E

the code will return {A},{A,B},{A,C},{A,C,D},{A,C,E}

where i actually need it to just return the branches i.e. {A,B},{A,C,D},{A,C,E}.

This doesn't have to be part of the method above, just as long as in the end the list i get is just the branches and not every path.

What I'm really trying to figure out is how to filter the IEnumerable list from the above method to only have entries where the last element in each list has no children.

So in my current code:

class Node
{
     public string Name;
     public int ParentID;
     public List<Node> Children;
}

and then in my main code

List<Node> listOfNodes = getTreeNodes();

Node rootNode = listOfNodes.Where(n => n.ParentID == 0).FirstOrDefault();
// the below paths var will have every path instead of just the branches
var paths = ComputePaths(rootNode, n=>n.Children);

Using the code from the linked answer:

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) {
    yield return new[] { Root };
    foreach (var Child in Children(Root)) 
        foreach (var ChildPath in ComputePaths(Child, Children)) 
            yield return new[] { Root }.Concat(ChildPath);            
}

Hope that makes sense. Any help would be greatly appreciated.

Upvotes: 2

Views: 2083

Answers (1)

Rob
Rob

Reputation: 27357

This works:

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) {
    var children = Children(Root);
    if (children != null && children.Any())
    {
        foreach (var Child in children) 
            foreach (var ChildPath in ComputePaths(Child, Children)) 
                yield return new[] { Root }.Concat(ChildPath);            
    } else {
        yield return new[] { Root };
    }
}

If the node is a leaf node (without children), we return itself. Otherwise, we return the path of its children.

Upvotes: 8

Related Questions