Select all family from root node using LINQ?

Question

Assume I have a Category which could have unlimited children and each child could also have unlimited children too.

Just curious, is there a way to retrieve all family of Root node using LINQ?

It sounds like you're asking if you can do recursion with linq? I would suggest looking at this http://stackoverflow.com/questions/4814242/linq-recursion-function — Nathan, Aug 08 '12 at 16:06
possible duplicate of [How to flatten tree via LINQ?](http://stackoverflow.com/questions/11830174/how-to-flatten-tree-via-linq) — L.B, Aug 08 '12 at 16:12

Sergey Kalinichenko · Accepted Answer · 2012-08-08T17:04:58.860

There are two common ways to process a recursive structure in C# - by using yield return and by writing a recursive function. I prefer the second way, here is an example:

public static class TreeUtils {
    public static IEnumerable<T> GetAllNodes<T>(
        this T node
    ,   Func<T,IEnumerable<T>> f) 
    {
        return GetAllNodes(new[] {node}, f);
    }
    public static IEnumerable<T> GetAllNodes<T>(
        this IEnumerable<T> e
    ,   Func<T,IEnumerable<T>> f) 
    {
        return e.SelectMany(c => f(c).GetAllNodes(f)).Concat(e);
    }
}

You can use this utility class as follows:

class TreeNode<T> {
    public T Content {get; set;}
    public IEnumerable<TreeNode<T>> Dependents {get;set;}
}

foreach (TreeNode node in TreeUtils.GetAllNodes(root, n => n.Dependents)) {
    Console.WriteLine(node.Content);
}

A somewhat cheating way would be to employ a "recursive" lambda:

using System;
using System.Collections.Generic;

public class Program {
    class Node {
        public int Data;
        public IEnumerable<Node> Dependents { get; set; }
    }
    public static void Main() {
        var root = Create(
            10
        ,   Create(5, Create(3), Create(7, Create(6), Create(8)))
        ,   Create(20, Create(15), Create(30, Create(28), Create(40)))
        );
        // We cannot combine the declaration and definition here
        Func<Node,IEnumerable<Node>> all = null;
        // The recursive magic is in the following line
        all = n => n.Dependents.SelectMany(d => all(d)).Concat(new[] {n});
        // Here is how you can use it
        foreach (var node in all(root)) {
            Console.WriteLine(node.Data);
        }
    }
    // Helper function for creating tree nodes
    private static Node Create(int data, params Node[] nodes) {
        return new Node { Data = data, Dependents = nodes };
    }
}

that's what i'm doing. i just curious if i could do it only in LINQ. — nonintanon, Aug 08 '12 at 16:17
@L.B Now it compiles and runs ([link](http://ideone.com/106j1)), both on Mono and .NET (I tested it locally). — Sergey Kalinichenko, Aug 08 '12 at 16:42
@nonintanon Take a look at the update. It does not require a separate recursive function, but it is not nearly as good-looking, and it takes more time to understand. — Sergey Kalinichenko, Aug 08 '12 at 17:06
Thanks @dasblinkenlight! SelectMany() seems to be very useful in this case. Look better than previous one tough :) — nonintanon, Aug 08 '12 at 18:31

score 1 · Answer 2 · answered Aug 08 '12 at 16:09

Lambdas, upon which linq is very dependent, don't support the recursion needed to do such a thing in an intuitive manner; however, using let and the y-combinator you can so it in a non-intuitive manner. Here is a complicated example:

http://blogs.msdn.com/b/lukeh/archive/2007/10/01/taking-linq-to-objects-to-extremes-a-fully-linqified-raytracer.aspx

Hopefully somebody will come up with a more concise one. If so, pick them.

Select all family from root node using LINQ?

2 Answers2