How can I get a List from all nodes in a tree using LINQ?

Question

Hi All,

How can I get a List from all nodes in a tree using LINQ?

My classes are:

class Node
{
 public class Node()
 {
  Children = new List<Node>();
 }

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

class Tree
{
 public Tree()
 {
  Roots = new List<Node>();
 }

 List<Node> Roots { get; set;}
}

Answer 1

Have a look here.

Answer 2

You can do this by either adding a traversal method, or by using recursive LINQ with Y-combinator. I personally prefer first approach.

Answer 3

class Node
    {
    public Node()
    {
        Children = new List<Node>();
    }

    public IEnumerable<Node> GetSubTree()
    {
        return Children.SelectMany(c => c.GetSubTree()).Concat(new[] { this });
        //Post-order traversal
    }

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

class Tree
{
    public Tree()
    {
        Roots = new List<Node>();
    }

    public IEnumerable<Node> GetAllNodes()
    {
        return Roots.SelectMany(root => root.GetSubTree());
    }

    List<Node> Roots { get; set; }
}

How can a tree have more than one root though? Isn't this a forest?

Answer 4

var allNodes = yourTree.Roots.SelectMany(x => x.TraverseTree(y => y.Children));

// ...

public static class EnumerableExtensions
{
    public static IEnumerable<T> TraverseTree<T>(
        this T parentNode, Func<T, IEnumerable<T>> childNodesSelector)
    {
        yield return parentNode;

        IEnumerable<T> childNodes = childNodesSelector(parentNode);
        if (childNodes != null)
        {
            foreach (T childNode in
                childNodes.SelectMany(x => x.TraverseTree(childNodesSelector)))
            {
                yield return childNode;
            }
        }
    } 
}

Answer 5

Start on Eric Lippert's blog from the link below:

http://blogs.msdn.com/b/ericlippert/archive/2010/04/19/every-binary-tree-there-is.aspx

This might be a more general discussion than you're looking for, but it will answer your question and a lot more besides...