Assign count of child leaf nodes to each parent in a hierarchical multidimensional array

Question

I have a nested array tree, generated from a flat array with the following function:

function convertToTree(
    array $flat,
    $idField = 'id',
    $parentIdField = 'parentId',
    $childNodesField = 'childNodes'
) {
    $indexed = array();
    // first pass - get the array indexed by the primary id  
    foreach ($flat as $row) {
        $indexed[$row[$idField]] = $row;
        $indexed[$row[$idField]][$childNodesField] = array();
    }

    //second pass  
    $root = null;
    foreach ($indexed as $id => $row) {
        $indexed[$row[$parentIdField]][$childNodesField][$id] =& $indexed[$id];
        if (!$row[$parentIdField]) {
            $root = $id;
        }
    }
    return array($root => $indexed[$root]);
}

My flat array:

$flat = [
    ['id' => 9, 'parentId' => NULL, 'name' => 'Item 0'],
    ['id' => 1, 'parentId' => 9, 'name' => 'Item 1'],
    ['id' => 10, 'parentId' => 1, 'name' => 'Item 10'],
    ['id' => 100, 'parentId' => 10, 'name' => 'Item 100'],
    ['id' => 101, 'parentId' => 10, 'name' => 'Item 101'],
    ['id' => 2, 'parentId' => 9, 'name' => 'Item 2'],
    ['id' => 20, 'parentId' => 2, 'name' => 'Item 20'],
    ['id' => 200, 'parentId' => 20, 'name' => 'Item 200'],
    ['id' => 201, 'parentId' => 20, 'name' => 'Item 201'],
];

I would need to add an entry "NUMBER OF LEAVES" for each node of my array. This entry should count ALL the leaves of all the subnodes of the node.

My expected result:

Array ( 
    [9] => Array ( 
        [id] => 9, 
        [parentId] => null,
        [name] => Item 0, 
        [NUMBER OF LEAVES] => 4,  (corresponding to leaves 100 and 101 + 200 and 201)
        [childNodes] => Array 
            ( 
                [1] => Array ( 
                    [id] => 1, 
                    [parentId] => 9, 
                    [name] => Item 1, 
                    [NUMBER OF LEAVES] => 2,   (corresponding to leaves 100 and 101)
                    [childNodes] => Array ( 
                        [10] => Array ( 
                            [id] => 10, 
                            [parentId] => 1, 
                            [name] => Item 10, 
                            [childNodes] => Array ( 
                                [100] => Array ( 
                                    [id] => 100, 
                                    [parentId] => 10, 
                                    [name] => Item 100, 
                                    [childNodes] => Array ( ) 
                                ) 
                                [101] => Array ( 
                                    [id] => 101, 
                                    [parentId] => 10, 
                                    [name] => Item 101, 
                                    [childNodes] => Array ( ) 
                                ) 
                            ) 
                        ) 
                    ) 
                ) 
                [2] => Array ( 
                    [id] => 2, 
                    [parentId] => 9, 
                    [name] => Item 2, 
                    [NUMBER OF LEAVES] => 2,   (corresponding to leaves 200 and 201)
                    [childNodes] => Array ( 
                        [20] => Array ( 
                            [id] => 20, 
                            [parentId] => 2, 
                            [name] => Item 20, 
                            [childNodes] => Array ( 
                                [200] => Array ( 
                                    [id] => 200, 
                                    [parentId] => 20, 
                                    [name] => Item 200, 
                                    [childNodes] => Array ( ) 
                                ) 
                                [201] => Array ( 
                                    [id] => 201, 
                                    [parentId] => 20, 
                                    [name] => Item 201, 
                                    [childNodes] => Array ( ) 
                                ) 
                            ) 
                        ) 
                    ) 
                ) 
            ) 
    ) 
)

Cristionna

Answer 1

You can do it easily as :

$leaves = 0;
array_walk_recursive($yourArray, function ($leaves) use (&$leaves) {
  $leaves++;
});

Example :

$foods = array(
  'fruits' => array('orange', 'banana', 'apple'),
  'veggie' => array('carrot', 'collard', 'pea')
);

$leaves = 0;
array_walk_recursive($foods, function ($leaves) use (&$leaves) {
  $leaves++;
});
echo $leaves; // will output 6

Lemire

You don't need to declare $leaves as passing it by reference will automatically declare it. – Proceeds

This script performs a generalized summing of leaf nodes in a multidimensional array, but do not attempt to satisfy the asked question. – Surplus

Answer 2

Answer to the primitive task that all other answerers chose to interpret:

You can leverage the native function array_walk_recursive() with a reference variable to carry the running total. Notice that the leafnode element itself doesn't need to be declared (because it is irrelevant to the anonymous function body) -- we only need to increment the reference variable on each iteration. (Demo)

$leaves = 0;
array_walk_recursive($array, function () use (&$leaves) {++$leaves;});
echo $leaves;

Alternatively, you can hand roll your own recursive leaf node counter as follows: (Demo)

function countLeafNodes(array $array): int {
    return array_reduce(
        $array,
        fn($result, $v) => $result + (is_array($v) ? countLeafNodes($v) : 1),
        0
    );
}
echo countLeafNodes($array);

...but these techniques just return a solitary integer value; not what you asked for.

---

Answer to your ACTUAL question:

I tried to adjust your function which converts the 2d payload to a tree, but wasn't successful. Instead, I'll provide a solution that traverses your tree structure and adds a leafChildren element to any non leaf node.

Recursively iterate your array and only inject the new leafChildren element if there is a non-zero count. My script will modify the input array by reference and return the total leaf children count. (Demo)

function countLeafNodes(array &$array): int {
    $totalChildren = 0;
    foreach ($array as &$row) {
        if ($row['childNodes']) {
            $totalChildren += $row['leafChildren'] = countLeafNodes($row['childNodes']);
            // move new element before `childNodes` element
            uasort($row, fn($a, $b) => is_array($a) <=> is_array($b));
        } else {
            ++$totalChildren;
        }
    }
    return $totalChildren;
}
countLeafNodes($array);
var_export($array);

Surplus