I know similar questions have been asked before but mine has some key differences that change it. So lets say I have a class with the following in C#

public class Node
    {
        public string Type { get; set; }

        public Node Parent { get; set; }

        public List<Node> Children { get; set; }
    }

And I have some sort of tree structure with types similar to this:

N1
  - N1
  - N1
N2
  - N3
  - N1
N3
N4
  - N5
      - N1
         -N6
N1
N1
  - N2

How do I filter by Type: N1 so the above tree looks like this:

N1
  - N1
  - N1
N2
  - N1
N4
  - N5
      - N1
N1
N1

Basically I want to filter by Type: N1 but leave the parent nodes if some child node has Type: N1. Im looking for simple C# method(s) that can achieve this, I do not want to add any library or anything. Something like: tree = FilterTree(type, ...)

CodePudding user response：

Here is a suggestion using recursion and a Func<Node, bool> delegate.

If you have a List<Node> tree, you could implement extension methods that are calling each other:

public static IEnumerable<Node> BuildTreeWithLeafNodes(
    this IEnumerable<Node> topNodes, 
    Func<Node, bool> leafNodeCondition)
{
    return topNodes
        .Select(topNode => topNode.GetSubTreeWithLeafNodes(leafNodeCondition))
        .Where(subTree => subTree != null);
}

public static Node GetSubTreeWithLeafNodes(
    this Node node, 
    Func<Node, bool> leafNodeCondition)
{
    if (node.Children != null && node.Children.Any())
    {
        node.Children = node.Children
            .BuildTreeWithLeafNodes(leafNodeCondition)
            .ToList();
    
        if (node.Children != null && node.Children.Any())
        {
            return node;
        }
    }
    
    return leafNodeCondition(node) ? node : null;
}

and get the filtered tree by calling:

var filteredTree = tree.BuildTreeWithLeafNodes(node => node.Type == "N1");

Example fiddle here.

What's happening?

BuildTreeWithLeafNodes() takes a collection of Nodes and returns a collection of Nodes where the following selection conditions apply for each node in the original collection:

• if the node is originally childless or none of the descendants satisfies the leafNodeCondition, the node (without children) is included in the return collection only if the node itself satisfies the leafNodeCondition.
• if the node originally has children and at least one of the descendants satisfies leafNodeCondition, the node's sub tree (node.Children with their descendants) is adjusted so that it only contains branches where the leaf node of each branch satisfies leafNodeCondition, and the node with the adjusted sub tree is included in the return collection.

The whole process can be visualized as a "descendant trimming" that is working itself up from each original leaf node and towards the top nodes (the original collection).

Basically, the way BuildTreeWithLeafNodes() and GetSubTreeWithLeafNodes() are calling each other, each original Node's sub trees (Children and their descendants) are being traversed all the way down to each respective sub tree's leaf node. If the leaf node does not satisfy the leafNodeCondition, it is removed from the parent node's Children. Once a parent node loses all its children (i.e. if none of the children satisfy the leafNodeCondition), the parent node itself will be removed from its own parent's Children unless it satisfies the leafNodeCondition.