Company Tree

result.json

[
  {
    "id": "uuid-1",
    "name": "Webprovise Corp",
    "cost": 42389,
    "children": [
      {
        "id": "uuid-2",
        "name": "Stamm LLC",
        "cost": 2587,
        "children": [
          {
            "id": "uuid-4",
            "name": "Price and Sons",
            "cost": 1203
          },
          {
            "id": "uuid-7",
            "name": "Zieme - Mills",
            "cost": 681
          },
          {
            "id": "uuid-19",
            "name": "Schneider - Adams",
            "cost": 109
          }
        ]
      },
      {
        "id": "uuid-3",
        "name": "Blanda, Langosh and Barton",
        "cost": 12468,
        "children": [
          {
            "id": "uuid-5",
            "name": "Hane - Windler",
            "cost": 1054
          },
          {
            "id": "uuid-6",
            "name": "Vandervort - Bechtelar",
            "cost": 1640
          },
          {
            "id": "uuid-9",
            "name": "Kuhic - Swift",
            "cost": 2180
          },
          {
            "id": "uuid-17",
            "name": "Rohan, Mayer and Haley",
            "cost": 3844
          },
          {
            "id": "uuid-20",
            "name": "Kunde, Armstrong and Hermann",
            "cost": 286
          }
        ]
      },
      {
        "id": "uuid-8",
        "name": "Bartell - Mosciski",
        "cost": 24542,
        "children": [
          {
            "id": "uuid-10",
            "name": "Lockman Inc",
            "cost": 3973
          },
          {
            "id": "uuid-11",
            "name": "Parker - Shanahan",
            "cost": 9879,
            "children": [
              {
                "id": "uuid-12",
                "name": "Swaniawski Inc",
                "cost": 1132
              },
              {
                "id": "uuid-14",
                "name": "Weimann, Runolfsson and Hand",
                "cost": 6580
              }
            ]
          },
          {
            "id": "uuid-13",
            "name": "Balistreri - Bruen",
            "cost": 1109
          },
          {
            "id": "uuid-15",
            "name": "Predovic and Sons",
            "cost": 3784
          },
          {
            "id": "uuid-16",
            "name": "Weissnat - Murazik",
            "cost": 3224
          }
        ]
      },
      {
        "id": "uuid-18",
        "name": "Walter, Schmidt and Osinski",
        "cost": 1933
      }
    ]
  },
  {
    "name": "Halvorson, Huels and Collier",
    "id": "NaN",
    "cost": 0
  }
]

test.php

<?php

abstract class Model
{
    const ENDPOINT = null;

    public static function all(): array
    {
        if (! static::ENDPOINT) {
            return [];
        }

        $data = json_decode(static::fetch(static::ENDPOINT), true) ?: [];

        $collection = [];

        foreach ($data as $value) {
            $collection[] = $value;
        }

        return $collection;
    }

    public static function fetch(string $url)
    {
        return file_get_contents($url);
    }
}

class Travel extends Model
{
    const ENDPOINT = 'https://5f27781bf5d27e001612e057.mockapi.io/webprovise/travels';
}

class Company extends Model
{
    const ENDPOINT = 'https://5f27781bf5d27e001612e057.mockapi.io/webprovise/companies';
}

class TestScript
{
    protected $children = [];

    public function execute()
    {
        $start = microtime(true);

        $companies = Company::all();

        $output = $this->buildTree($companies, $this->costs());

        echo json_encode($output);
        echo "<br>";
        echo 'Total time: '.  (microtime(true) - $start);
    }

    protected function costs(): array
    {
        $costs = [];

        foreach (Travel::all() as $travel) {
            if (isset($costs[$travel['companyId']])) {
                $costs[$travel['companyId']] += $travel['price'] ?? 0;
            } else {
                $costs[$travel['companyId']] = 0;
            }
        }

        return $costs;
    }

    protected function buildTree(array $elements, array $costs, $parentId = 0)
    {
        $output = [];

        foreach ($elements as $element) {
            if ($element['parentId'] == $parentId && ! in_array($element['id'], array_unique($this->children))) {
                $this->children[] = $element['id'];
                $element['cost'] = $costs[$element['id']] ?? 0;
                $children = $this->buildTree($elements, $costs, $element['id']);

                if ($children) {
                    $element['children'] = $children;
                    $element['cost'] += array_reduce($children, function ($carry, $item) {
                        return $carry += $item['cost'] ?? 0;
                    }, 0);
                }

                unset($element['createdAt']);
                unset($element['parentId']);
                $output[] = $element;
            }
        }

        return $output;
    }
}

(new TestScript())->execute();