Create a Tree from a list of items, when each item contains a reference to its parent

c#, linq, tree

Solution

`ToLookup` can trivially create a lookup of all children for each item. Once you have that you can map each item to the new object and have an easy mechanism to get all of the children for each item.

IEnumerable<Foo> data = GetData();
var lookup = data.ToLookup(foo => foo.Parent);
Func<Foo, TreeItem<object>> selector = null;
selector = foo => new TreeItem<object>()
{
    Item = foo,
    Children = lookup[foo].Select(selector),
};
var rootNodes = lookup[null].Select(selector);

Or, if you'd rather avoid recursion, you can transform each item when building the lookup without mapping the children and then mutate each item to include the children later:

IEnumerable<Foo> data = GetData();
var lookup = data.ToLookup(foo => foo.Parent,
    foo => new TreeItem<object>() { Item = foo });
foreach (var node in lookup.SelectMany(x => x))
    node.Children = lookup[node.Item];
var rootNodes = lookup[null];

The lack of recursion may matter if there is a lot of data, and it also allows it to handle arbitrary graphs, not just trees. (In particular it can handle cycles.)

Problem

I have a list of objects of type `Foo`. Each `Foo` object contains a reference to its parent: ``` public class Foo { public Foo Parent { get; set; } } ``` (If `Parent` is null, then the `Foo` is considered to be a 'root' node.) As you can see, this implies a sort of "bottom-up" tree hierarchy. I would like to flip this child->parent association upside-down by wrapping my `Foo` objects in a new class called `TreeItem`; ``` public class TreeItem<T> { public T Item { get; set; } public IEnumerable<TreeItem<T>> Children { get; set; } } ``` As illustrated, this would give me a more natural "top-down" tree hierarchy. I believe this would allow for much easier data binding, eg. in a WPF `TreeView`. Is there a concise Linq statement which would be able to take a `List<Foo>`, find each `Foo` object's children, and spit out the correspondingly-converted list of `TreeItem<Foo>`? Barring a Linq query, what would be the simplest algorithm? Bonus: What words or search terms would you use, to describe this "tree-flipping" transformation?

Original source