Сортировка иерархии с полями пути и глубины с помощью Linq

Хорошо, сначала вы действительно должны добавить следующее ограничение

interface ITree<T>
    where T : class, ITree<T>
{
    // ...
}

поэтому мы можем безопасно перемещаться по иерархии, используя свойства Parent и Children без приведения.

Во-вторых, вместо того, чтобы заново изобретать колесо, я буду повторно использовать общее дерево для вспомогательного метода обхода порядка из моего ответа на Как сгладить дерево с помощью LINQ? (и пара других):

public static partial class TreeUtils
{
    public static IEnumerable<T> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

С этим помощником в кармане рассматриваемый метод прост:

partial class TreeUtils
{
    public static IEnumerable<T> Ordered<T>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<T>> order = null)
        where T : class, ITree<T>
    {
        if (order == null) order = items => items.OrderBy(item => item.Name);
        return order(source.Where(item => item.Parent == null))
            .Expand(item => item.Children != null && item.Children.Any() ? order(item.Children) : null);
    }
}

Пример использования:

List<TreeItem> flatList = ...;
var orderedList = flatList.Ordered().ToList();

ОБНОВЛЕНИЕ: то же самое, только с использованием свойств Path и Id:

public static partial class TreeUtils
{
    public static IEnumerable<T> Ordered<T>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<T>> order = null)
        where T : class, ITree<T>
    {
        if (order == null) order = items => items != null && items.Any() ?  items.OrderBy(item => item.Name) : null;
        var chldrenByParentId = source
            .Select(item => new { item, path = item.Path.Split('.') })
            .ToLookup(e => e.path.Length >= 2 ? int.Parse(e.path[e.path.Length - 2]) : (int?)null, e => e.item);
        return (order(chldrenByParentId[null]) ?? Enumerable.Empty<T>())
            .Expand(item => order(chldrenByParentId[item.Id]));
    }
}