Linq recursive search nodes

Question

Trying to get in the end List of all List<Node>() that is not null. How to do this with child nodes?

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

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

public class Program
{
    static void Main(string[] args)
    {
        List<Node> Items = new List<Node>();
        Items.Add(new Node { Name = "Test0" });
        Items.Add(new Node { Name = "Test1" });
        Items.Add(new Node { Name = "Test2" });
        Items.Add(new Node { Name = "Test3" });
        Items.Add(new Node { Name = "Test4" });
        Items.Add(new Node { Name = "Test5" });
        Items.Add(new Node
        {
            Name = "Test6",
            Nodes = new List<Node>
            {
                new Node
                {
                    Name = "Test6.1",
                    Nodes = new List<Node>
                    {
                        new Node
                        {
                            Name = "Test6.1.1", Nodes = new List<Node>()
                        }
                    }
                },

            }
        });
        Items.Add(new Node { Name = "Test7", Nodes = new List<Node> { } });
        Items.Add(new Node { Name = "Test8", Nodes = new List<Node> { } });

        var NotNullNodes = Items.SelectMany(m => m.Nodes);
    }
}

you would need a method that does this recursion. something like in [this post](https://bitlush.com/blog/recursive-select-in-c-sharp-and-linq) or you simply use a stack like in this [possible duplicate](https://stackoverflow.com/questions/20974248/recursive-hierarchy-recursive-query-using-linq) — Mong Zhu, May 06 '19 at 08:22
on the theoretical perspective there are many ways to look for your nodes. It is called traversal of a tree structure. It would be worth to have a look at [this article](https://en.wikipedia.org/wiki/Tree_traversal) — Mong Zhu, May 06 '19 at 08:24
does it have to be recursive? are you trying to learn recursion? Linq on itself, will not traverse your tree. You need to do this — Mong Zhu, May 06 '19 at 08:34

score 3 · Accepted Answer · answered May 06 '19 at 09:17

Another linq recursive solution:

public static IEnumerable<Node> GetAllNodes( Node root )
{
    if( root == null )
    {
        yield break;
    }

    yield return root;

    if ( root.Nodes == null )
    {
        yield break;
    }

    foreach ( Node descendant in root.Nodes.SelectMany( GetAllNodes ) )
    {
        yield return descendant;
    }
}

Use like this:

Items.SelectMany( GetAllNodes )

Dmitry Bychenko · Answer 2 · 2019-05-06T09:26:45.640

Well, SelectMany flattens one level in depth only; in your case you want some kind of search on graphs, e.g. BFS - Breadth First Search:

  public static partial class EnumerableExtensions {
    public static IEnumerable<T> BreadthFirstSearch<T>(
      this IEnumerable<T> source, 
      Func<T, IEnumerable<T>> children) {

      if (Object.ReferenceEquals(null, source))
        throw new ArgumentNullException(nameof(source));
      else if (Object.ReferenceEquals(null, children))
        throw new ArgumentNullException(nameof(children));

      HashSet<T> proceeded = new HashSet<T>();

      Queue<IEnumerable<T>> queue = new Queue<IEnumerable<T>>();

      queue.Enqueue(source);

      while (queue.Count > 0) {
        IEnumerable<T> src = queue.Dequeue();

        if (Object.ReferenceEquals(null, src))
          continue;

        foreach (var item in src) 
          if (proceeded.Add(item)) {
            yield return item;

            queue.Enqueue(children(item));
          }
      }
    }
  }

then you can put

var NotNullNodes = Items.BreadthFirstSearch(item => item.Items ?? new List<Node>());

score 0 · Answer 3 · answered May 06 '19 at 08:37

Here's a function that recursively takes all nodes:

    public static List<Node> GetAllNodes(List<Node> items)
    {
        List<Node> allNodes = new List<Node>();

        foreach(Node n in items)
            if (n.Nodes != null && n.Nodes.Count > 0)
                allNodes.AddRange(GetAllNodes(n.Nodes));

        allNodes.AddRange(items);

        return allNodes;
    }

score 0 · Answer 4 · answered May 06 '19 at 19:06

If you create an extension method for IEnumerable, then you can use it as if it was an existing LINQ method. See extension methods demystified

static IEnumerable<Node> Flatten(IEnumerable<node> nodesWithSubNodes)
{
    // Todo: check nodesWithSubNodes not null
    foreach (var node in nodesWithSubNodes)
    {
        yield return node;
        if (node.SubNodes != null)  // not needed if you are certain that not null
        {
            foreach (var subNode in nodes.SubNodes.Flatten())
                yield return subNode;
        }
}

Usage:

var result = myNodes.Flatten()
             .Take(3)
             .ToList();

The nice thing about this is that it looks like an existing LINQ function. It is also very efficient, because it does not enumerate more elements than you actually query, as in the example.

Linq recursive search nodes

4 Answers4

Linked