Searching a tree using LINQ

Question

I have a tree created from this class.

class Node {     public string Key { get; }     public List<Node> Children { get; } } 

I want to search in all children and all their children to get the ones matching a condition:

node.Key == SomeSpecialKey 

How can I implement it?

Answer 1

It's a misconception that this requires recursion. It will require a stack or a queue and the easiest way is to implement it using recursion. For sake of completeness I'll provide a non-recursive answer.

static IEnumerable<Node> Descendants(this Node root) {     var nodes = new Stack<Node>(new[] {root});     while (nodes.Any())     {         Node node = nodes.Pop();         yield return node;         foreach (var n in node.Children) nodes.Push(n);     } } 

Use this expression for example to use it:

root.Descendants().Where(node => node.Key == SomeSpecialKey)