The sum value of all nodes in the tree array in php

Question

I have flat array like:

[
    {
        "id": "1",
        "parentId": "0",
        "cost": 1000
    },
    {
        "id": "2",
        "parentId": "1",
        "cost": 2000
    },
    {
        "id": "3",
        "parentId": "2",
        "cost": 4000
    },
    ...
]

Requirement:

• convert flat array to tree array --> (DONE)
• sum of each id is the total price of it and its child

now the problem appears:

• should summation be done before or after converting from flat array to tree array

This is my code is try convert flat to tree:

public function buildTree(array $flat)
    {
        $grouped = [];
        $fnBuilder = function ($companies) use (&$fnBuilder, $grouped) {
            foreach ($companies as $k => $company) {
                $id = $company['id'];
                if (isset($grouped[$id])) {
                    $company['children'] = $fnBuilder($grouped[$id]);
                }
                $companies[$k] = $company;
            }
            return $companies;
        };
        return $fnBuilder($grouped[0]);
    }

My expect result is like:

[
    {
        "id": "1",
        "sum": 7000,
        "children": [
            {
                "id": "2",
                "sum": 6000,
                "children": [
                    {
                        "id": "3",
                        "sum": 4000,
                    },

I wonder if it's possible to handle the summing inside the buildTree?

My idea is to have a tree and then handle the sum of sublevels, but i can't handle assigning the sum to the parent element

Answer 1

You could build the tree without recursion, and then use recursion to update the sum, in post-order depth first order:

function buildTree(array $flat) {
    foreach ($flat as ["id" => $id, "cost" => $sum]) {
        $keyed[$id] = ["id" => $id, "sum" => $sum];
    }
    foreach ($flat as ["id" => $id, "parentId" => $parentId]) {
        if (isset($keyed[$parentId])) {
            $keyed[$parentId]["children"][] = &$keyed[$id]; 
        } else {
            $root = &$keyed[$id];
        }
    }
    function updateSum(&$node) {
        foreach ($node["children"] ?? [] as &$child) {
            $node["sum"] += updateSum($child);
        }
        return $node["sum"];
    }
    updateSum($root);
    return $root;
}

Example run:

$flat = json_decode('[
    {
        "id": "1",
        "parentId": "0",
        "cost": 1000
    },
    {
        "id": "2",
        "parentId": "1",
        "cost": 2000
    },
    {
        "id": "3",
        "parentId": "2",
        "cost": 4000
    }
]', true);

$root = buildTree($flat);
print_r($root);