Tengo la siguiente estructura:

MyClass {
  guid ID
  guid ParentID
  string Name
}

Me gustaría crear una matriz que contenga los elementos en el orden en que deberían mostrarse en una jerarquía (por ejemplo, de acuerdo con sus valores "izquierdos"), así como un hash que asigna el guid al nivel de sangría.

Por ejemplo:

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

Esto esencialmente produciría los siguientes 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 mayor claridad, así es como se ve la jerarquía:

Airplane
Animal
  Cats
    Tiger
Book

Me gustaría recorrer los elementos la menor cantidad de veces posible. Tampoco quiero crear una estructura de datos jerárquica. Prefiero usar matrices, hashes, pilas o colas.

Los dos objetivos son:

Almacene un hash de la ID en el nivel de sangría.Ordene la lista que contiene todos los objetos de acuerdo con sus valores izquierdos.

Cuando obtengo la lista de elementos, no están en un orden particular. Los hermanos deben ser ordenados por su propiedad Nombre.

Actualizar: Esto puede parecer que no he intentado encontrar una solución yo mismo y simplemente quiero que otros hagan el trabajo por mí. Sin embargo, he intentado encontrar tres soluciones diferentes, y me he quedado atascado en cada una. Una razón podría ser que he tratado de evitar la recurrencia (tal vez erróneamente). No estoy publicando las soluciones parciales que tengo hasta ahora, ya que son incorrectas y pueden influir gravemente en las soluciones de los demás.