Interesting problem. At first I wondered if it would be possible using a simple Linq query construction with some selector delegates, but that gets messy quite quickly.
The below simple linq construction gets you part of the way, but really requires use and propagation of counts and original input order as well.
// Simple Linq, but just not good enough
// Need to also propagate original input order and count the number of siblings
Func<IEnumerable<Item>, Item, IEnumerable<Item>> SelectSuccessors = (set, item) => set.Where(i => i.ID == item.nextID);
Func<IEnumerable<Item>, IEnumerable<Item>, IEnumerable<Item>> Flatten = null;
Flatten = (set, sibblingPool) => set
.SelectMany(i => new[] { i }.Concat(Flatten(SelectSuccessors(sibblingPool.Except(set), i), sibblingPool.Except(set))));
var unparented = items.Where(i => !items.Any(n => n.nextID == i.ID));
foreach (var item in Flatten(unparented, items))
Console.WriteLine(item.ID);
Its result is ["X", "C", "B", "A", "D", "E"]
A very different type of construction is to really capture the recursive structure of this problem, in a self recursive data structure:
public class ItemHierarchy : Tuple<Item, int, List<ItemHierarchy>>
{
public static List<ItemHierarchy> BuildHierarchy(IEnumerable<Item> items)
{
var inputOrderNumbered = items.Select((item, order) => Tuple.Create(item, order));
var roots = inputOrderNumbered.Where(i => !items.Any(n => n.nextID == i.Item1.ID));
return roots.Select(r => BuildFor(r.Item1, r.Item2, inputOrderNumbered.Except(roots))).ToList();
}
public Item Item
{
get { return this.Item1; }
}
public int OriginalInputOrder
{
get { return this.Item2; }
}
public int NumberOfDescendents
{
get { return this.Item3.Count + this.Item3.Sum(i => i.NumberOfDescendents); }
}
public IEnumerable<Item> Flattened
{
get { return new[] { this.Item }.Concat(Descendents); }
}
public List<ItemHierarchy> DescendentHierarchy
{
get { return this.Item3; }
}
public IEnumerable<Item> Descendents
{
get { return this.Item3.SelectMany(i => new [] { i.Item }.Concat(i.Descendents)); }
}
public IEnumerable<Item> Leafs
{
get
{
if (NumberOfDescendents == 0)
return new[] { this.Item };
else
return DescendentHierarchy.SelectMany(d => d.Leafs);
}
}
protected ItemHierarchy(Item item, int originalOrder, IEnumerable<Tuple<Item, int>> descendents, IEnumerable<Tuple<Item, int>> remaining)
: base(item, originalOrder, descendents.Select(d => BuildFor(d.Item1, d.Item2, remaining)).ToList())
{
}
private static ItemHierarchy BuildFor(Item item, int originalOrder, IEnumerable<Tuple<Item, int>> numberedSiblings)
{
var descendents = numberedSiblings.Where(s => s.Item1.ID == item.nextID);
return new ItemHierarchy(item, originalOrder, descendents, numberedSiblings.Except(descendents));
}
}
Which can then be used to solve the problem you posed as:
// This works quite well.
// As a bonus it preserves the original input information
// and offers a navigatable/queryable hierarchy.
var hierarchy = ItemHierarchy.BuildHierarchy(items);
foreach (var item in hierarchy.OrderBy(r => r.NumberOfDescendents).ThenBy(r => r.OriginalInputOrder).SelectMany(r => r.Flattened))
Console.WriteLine(item.ID);