Destroy tree branches where end nodes meet certain criteria

Question

I have a TreeNode class as follows:

 public class TreeNode { public enum NodeType { Root,Element, Category} public TreeNode() { Children = new List<TreeNode>(); } public List<TreeNode> Children { get; set; } public string Name { get; set; } public NodeType Type { get; set; } } 

And I have a BuildTree method that fills in the setup of the tree structure node Name and type for each node (for example, the First node will be set to Root Type, and the child nodes can be either Element or category types).

I am looking for an efficient way (possibly using LINQ) to prune tree branches where the final type node is not of type Category. Any ideas on how to achieve this?

Here is a visual example:

Before

 Root | |_ NodeA (Element) |_ Node B (Element) | |_ Node B.1 (Category) |_ Node C (Element) | |_ Node C.1 (Element) | |_Node C.1.1 (Category) |_ Node D (Element) |_Node D.1 (Element) 

After :

 Root | |_ Node B (Element) | |_ Node B.1 (Category) |_ Node C (Element) |_ Node C.1 (Element) |_Node C.1.1 (Category) 

Thanks in advance!

Answer 1

First we need to describe how to make the first aggregation of the depth of the tree:

 //seed: leafNode -> accumulate //func: interiorNode, children accumulates -> accumulate public static TAccumulate Aggregate<TAccumulate>( this TreeNode root, Func<TreeNode, TAccumulate> seed, Func<TreeNode, List<TAccumulate>, TAccumulate> func) { if (root.Children == null || !root.Children.Any()) return seed(root); return func(root, children.Select(child => child.Aggregate(seed, func)).ToList()); } 

Then we can use this to make a modification, such as requested by you:

 tree.Aggregate( leaf => new { Keep = leaf.NodeType == TreeNode.NodeType.Category, Node = leaf }, (node, children) => { var removal = new HashSet<TreeNode>( children.Where(child => !child.Keep).Select(child => child.Node)); node.Children.RemoveAll(removal.Contains); return new { Keep = children.Any(child => child.Keep), Node = node }; }); 

This provides a concise, declarative way to describe which transformation you want to apply to your tree without going into details of the workaround in the description of the transformation.

Answer 2

This is not that complex; you just need a recursive tree traversal. The main case is that the node itself is a category. Then simply call the function for each of the children and save those that have a category among their children.

 /// <summary> /// Removes all child nodes that do not have at least one Category as a child. /// </summary> /// <param name="node">The node to alter the children of.</param> /// <returns>True if there is at least one Category in this subtree</returns> public static bool RemoveEmptyElements(TreeNode node) { if (node.Type == TreeNode.NodeType.Category) return true; node.Children = node.Children.Where(child => RemoveEmptyElements(child)) .ToList(); return node.Children.Any(); } 

Answer 3

You can simply use post-order to move around the tree. When you return to the second level of the tree without finding a sheet of type category. Go again from this node to remove all leaves rooted from it.