CODEWITHSUNDEEP
c#linq
gumby
gumby

Reputation: 187

How to iterate a tree structure with logic on where to stop

Given a class;

public class TreeNode
{
    public string nodeType;
    public string nodeName;
    public List<TreeNode> Children;
}

instantiated by ;

var tree = new TreeNode()
            {
                nodeName = "Fred",
                Children = new List<TreeNode>()
                {
                    new TreeNode() { nodeName = "James" },
                    new TreeNode()
                    {
                        nodeName = "Lucy",
                        Children = new List<TreeNode>()
                        {
                            new TreeNode() { nodeName = "James",
                                Children = new List<TreeNode>()
                                {
                                    new TreeNode() { nodeName = "Bob" },
                                    new TreeNode() { nodeName = "Kevin" },
                                } },
                            new TreeNode() { nodeName = "Kevin" }
                        }
                    }

                }
             };

How would I go about filtering the list by "James" and return the tree as a collection like ;

Fred - James
Fred - Lucy - James

The smarts is that it does not need to include any child node of the filter criteria. I would like to use linq if possible but not sure if its possible.

Thanks

Upvotes: 0

Views: 88

Answers (1)

Enigmativity
Enigmativity

Reputation: 117175

Here you go:

IEnumerable<TreeNode[]> Flatten(TreeNode node) =>
    (node.Children ?? new List<TreeNode>())
        .SelectMany(child => Flatten(child))
        .Select(nodes => nodes.StartWith(node).ToArray())
        .StartWith(new[] { node });

IEnumerable<TreeNode[]> results =
    Flatten(tree)
        .Where(nodes => nodes.Last().nodeName == "James");

string text =
    String.Join(
        Environment.NewLine,
        results.Select(nodes =>
            String.Join(
                " - ",
                nodes.Select(node => node.nodeName))));

That gives me:

Fred - James
Fred - Lucy - James

Here's a version that doesn't require Microsoft's System.Interactive NuGet package:

IEnumerable<TreeNode[]> Flatten(TreeNode node) =>
    new[] { new[] { node } }
        .Concat(
            (node.Children ?? new List<TreeNode>())
                .SelectMany(child => Flatten(child))
                .Select(nodes => new[] { node }.Concat(nodes).ToArray()));

Upvotes: 1

Related Questions