<?php
$array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'subroot 2-1'],
  ['level'=>3, 'name' => '__subroot 2-1/1'],
  ['level'=>2, 'name' => 'subroot 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

function benchmark(callable $function, $args = null, $count = 1) {
   $time = microtime(true);

   for($i=0; $i<$count; $i++) {
      $result = is_array($args)?
                call_user_func_array($function, $args):
                call_user_func_array($function);
   }

   return [
      'count' => $count,
      'total'   => microtime(true) - $time,
      'average' => (microtime(true) - $time) / $count
   ];
}

function generateParentIdentifiers(array $array) {
    $length = count($array);

    for ($i = 0; $i < $length; $i++) {
        $current = &$array[$i];
        $current['parent'] = 0;

        for ($j = $i; $j >= 0; $j--) {
            if ($current['level'] - $array[$j]['level'] === 1) {
                $current['parent'] = $j;
                break;
            }
        }
    }

    return $array;
}

function buildTree(array $array) {
    $nodes = generateParentIdentifiers($array);
    $tree = [];

    foreach ($nodes as &$node) {
        $node['children'] = [];

        if ($node['parent'] !== 0) {
            $nodes[$node['parent']]['children'][] = &$node;
        } else {
            $tree[] = &$node;
        }
    }

    return $tree;
}
echo '<pre>';
var_dump(benchmark('buildTree', [$array], 1000000));