Algoritmo para converter dados simples hierárquicos (com ParentID) em lista simples classificada com níveis de indentação

Eu tenho a seguinte estrutura:

MyClass {
  guid ID
  guid ParentID
  string Name
}

Gostaria de criar uma matriz que contenha os elementos na ordem em que devem ser exibidos em uma hierarquia (por exemplo, de acordo com seus valores "esquerdos"), bem como um hash que mapeia o guid para o nível de indentação.

Por exemplo:

ID     Name     ParentID
------------------------
1      Cats     2
2      Animal   NULL
3      Tiger    1
4      Book     NULL
5      Airplane NULL

Isso essencialmente produziria os seguintes objetos:

// Array is an array of all the elements sorted by the way you would see them in a fully expanded tree
Array[0] = "Airplane"
Array[1] = "Animal"
Array[2] = "Cats"
Array[3] = "Tiger"
Array[4] = "Book"

// IndentationLevel is a hash of GUIDs to IndentationLevels.
IndentationLevel["1"] = 1
IndentationLevel["2"] = 0
IndentationLevel["3"] = 2
IndentationLevel["4"] = 0
IndentationLevel["5"] = 0

Para maior clareza, é assim que a hierarquia se parece:

Airplane
Animal
  Cats
    Tiger
Book

Eu gostaria de percorrer os itens o mínimo de vezes possível. Também não quero criar uma estrutura de dados hierárquica. Eu preferiria usar matrizes, hashes, pilhas ou filas.

Os dois objetivos são:

Armazene um hash do ID no nível de indentação.Classifique a lista que contém todos os objetos de acordo com os valores à esquerda.

Quando recebo a lista de elementos, eles não estão em uma ordem específica. Os irmãos devem ser ordenados por sua propriedade Nome.

Atualizar: Pode parecer que eu ainda não tentei encontrar uma solução e simplesmente quero que os outros façam o trabalho por mim. No entanto, tentei encontrar três soluções diferentes e fiquei presa em cada uma. Um motivo pode ser o fato de eu ter tentado evitar recursões (talvez de maneira errada). Não estou postando as soluções parciais que tenho até agora, pois elas estão incorretas e podem influenciar muito as soluções de outras pessoas.

questionAnswers(3)

yourAnswerToTheQuestion