rafuck

Еще вариант, менее "классический" что ли.. Побольше памяти будет есть, но не зависит от сортировки.

function flat2tree(&$flat){
    $tree = array();
    $nodeMap = array();
    
    $N = (is_array($flat)) ? count($flat) : 0;

    for ($i=0; $i<$N; ++$i){
        $node =& $flat[$i];
        
        if (isset($nodeMap[$node['pid']])){
            $parent =& $nodeMap[$node['pid']];
            if (!isset($parent['child']) || !is_array($parent['child'])){
                $parent['child'] = array();
            }
            $parent['child'][] = $node;
            $nodeMap[$node['id']] =& $parent['child'][count($parent['child']) - 1];
        }
        else{
            $tree[] = $node;
            $nodeMap[$node['id']] =& $tree[count($tree) - 1];
        }
    }

    return $tree;
}

$flat = array(
    array('id' => 1, 'pid' => null, 'name' => 'ipsum'),
    array('id' => 2, 'pid' => 1, 'name' => 'ipsum1'),
    array('id' => 3, 'pid' => 1, 'name' => 'ipsum2'),
    array('id' => 4, 'pid' => 2, 'name' => 'ipsum3'),
    array('id' => 5, 'pid' => 3, 'name' => 'ipsum4'),
    array('id' => 6, 'pid' => null, 'name' => 'ipsum5')
);
$tree = flat2tree($flat);
var_dump($tree);
echo json_encode($tree);

Вот, собственно, код. Узлы в плоской таблице должны быть отсортированы в порядке ЛВП обхода (а не как у вас, в ширину - см. пример). Если сортировка в ширину критична, то алгоритм будет другой.

function flat2tree(&$flat){
    $tree = array();
    $path = array();
    $pathLength = 0;
    
    $N = (is_array($flat)) ? count($flat) : 0;

    for ($i=0; $i<$N; ++$i){
        $node =& $flat[$i];
        for(; $pathLength && $path[$pathLength-1]['id'] != $node['pid']; --$pathLength);

        if ($pathLength){
            $parent =& $path[$pathLength-1];
            if (!isset($parent['child']) || !is_array($parent['child'])){
                $parent['child'] = array();
            }
            $parent['child'][] = $node;
            $path[$pathLength++] =& $parent['child'][count($parent['child']) - 1];
        }
        else{
            $tree[] = $node;
            $path[$pathLength++] =& $tree[count($tree) - 1];
        }
    }

    return $tree;
}

$flat = array(
    array('id' => 1, 'pid' => null, 'name' => 'ipsum'),
    array('id' => 2, 'pid' => 1, 'name' => 'ipsum1'),
    array('id' => 4, 'pid' => 2, 'name' => 'ipsum3'),
    array('id' => 3, 'pid' => 1, 'name' => 'ipsum2'),
    array('id' => 5, 'pid' => 3, 'name' => 'ipsum4'),
    array('id' => 6, 'pid' => null, 'name' => 'ipsum5')
);
$tree = flat2tree($flat);
var_dump($tree);
echo json_encode($tree);