La forma más fácil de construir un árbol a partir de una lista de antepasados

La primera clave es ordenar los resultados de SQL por el número de antepasados. Hice esto en PHP porque evito las complejidades de los números de varios dígitos.

Esto proporciona una lista de nodos en un orden en el que se pueden insertar de forma válida.

Array
(
    [1] => Array
        (
            [0] => 1
        )

    [4] => Array
        (
            [0] => 4
            [1] => 1
        )

    [2] => Array
        (
            [0] => 2
            [1] => 1
        )

    [3] => Array
        (
            [0] => 3
            [1] => 1
            [2] => 2
        )

)

En este punto, no me importan las claves, solo las listas de antepasados. El camino a través del árbol se puede encontrar entre la intersección de los nodos disponibles y los ancestros restantes.

  function add_node($ancestors, &$tree) {
    if (count($ancestors) == 1) {
      $tree[array_pop($ancestors)] = array();
      return;
    }   
    $next_node = array_intersect($ancestors, array_keys($tree));
    $this->add_node(
        array_diff($ancestors, $next_node) , 
        $tree[array_pop($next_node)]
        );  
  }