Recursivly ordenate array con id y estructura parent_id

Entonces, obtuve esta matriz (recostackción de datos de una base de datos):

Array ( [0] => Array ( [id] => 1 [parent_id] => 0 ) [1] => Array ( [id] => 2 [parent_id] => 0 ) [2] => Array ( [id] => 3 [parent_id] => 2 ) [3] => Array ( [id] => 4 [parent_id] => 2 ) [4] => Array ( [id] => 5 [parent_id] => 4 ) ) 

y estoy tratando de crear y ordenar una matriz como esta:

 Array ( [1] => Array ( [parent_id] => 0 ) [2] => Array ( [parent_id] => 0 [children] => Array ( [3] => Array ( [parent_id] => 2 ) [4] => Array ( [parent_id] => 2 [children] => Array ( [5] => Array ( [parent_id] => 4 ) ) ) ) ) ) 

y probé con el siguiente código:

 function placeInParent(&$newList, $item) { if (isset($newList[$item['parent_id']])) { $newList[$item['parent_id']]['children'][$item['id']] = $item; return true; } foreach ($newList as $newItem) { if (isset($newItem['children'])) { if (placeInParent($newItem['children'], $item)) { return true; } } } return false; } $oldList = (first array above) $newList = array(); foreach ($oldList as $item) { if ($item['parent_id'] == 0) { $newList[$item['id']] = $item; } else { placeInParent($newList, $item); } } 

¡pero el problema es que solo obtengo los primeros 2 niveles de la matriz! El último se perdió … y mi matriz ordenada resulta así:

 Array ( [1] => Array ( [parent_id] => 0 ) [2] => Array ( [parent_id] => 0 [children] => Array ( [3] => Array ( [parent_id] => 2 ) [4] => Array ( [parent_id] => 2 ) ) ) ) 

Simplemente no puedo llegar a donde estoy metiendo la pata: \ help?

Puede hacerlo sin recurrencia con la ayuda de un índice que hace referencia a los nodos dentro del árbol:

 $arr = array( array('id'=>1, 'parent_id'=>0), array('id'=>2, 'parent_id'=>0), array('id'=>3, 'parent_id'=>2), array('id'=>4, 'parent_id'=>2), array('id'=>5, 'parent_id'=>4), ); // array to build the final hierarchy $tree = array( 'children' => array(), 'path' => array() ); // index array that references the inserted nodes $index = array(0=>&$tree); foreach ($arr as $key => $val) { // pick the parent node inside the tree by using the index $parent = &$index[$val['parent_id']]; // append node to be inserted to the children array $node = array( 'parent_id' => $val['parent_id'], 'path' => $parent['path'] + array($val['id']) ); $parent['children'][$val['id']] = $node; // insert/update reference to recently inserted node inside the tree $index[$val['id']] = &$parent['children'][$val['id']]; } 

La matriz final que está buscando está en $tree['children'] .