Get parent and leaf ids from tree builder

I’m building a tree feature for my app. My tree has infinite level. I’m using this functions to build my tree (you can try my code here https://onlinephp.io/c/a50bc):

function build(array $array): array
{
    if (count($array) <= 0) {
        return [
            'leaf_ids'   => [],
            'parent_ids' => [],
            'tree'       => [],
        ];
    }

    $groupByParent = [];
    foreach ($array as $arr) {
        $parent_id = empty($arr['parent_id']) ? 0 : $arr['parent_id'];
        $groupByParent[$parent_id][] = $arr;
    }

    return makeTree($groupByParent, $groupByParent[0]);
}

 function makeTree(array &$parentList, array $items): array
{
    $tree = [];
    $leafIds = [];
    $parentIds = [];

    foreach ($items as $item) {
        if (isset($parentList[$item['id']])) {
            $item['children'] = makeTree($parentList, $parentList[$item['id']])['tree'];
        }

        if (!isset($item['children'])) {
            $leafIds[] = $item['id'];
        } else {
            $parentIds[] = $item['id'];
        }

        $tree[] = $item;
    }

    return ['tree' => $tree, 'leaf_ids' => $leafIds, 'parent_ids' => $parentIds];
}

$array = [
    [   
        'id' => 1,
        'parent_id' => NULL,
        'value' => 'Hi',
    ],
    [   
        'id' => 2,
        'parent_id' => NULL,
        'value' => 'Bye',
    ],
    [   
        'id' => 3,
        'parent_id' => 1,
        'value' => 'Hey',
    ],
    [   
        'id' => 4,
        'parent_id' => 1,
        'value' => 'Hello',
    ],
    [   
        'id' => 5,
        'parent_id' => 2,
        'value' => 'Cya',
    ],
    [   
        'id' => 6,
        'parent_id' => 5,
        'value' => 'Byebye',
    ],
];

print_r(json_encode(build($array), JSON_PRETTY_PRINT));

I’d like to get the list of leafs and parents but my code doesn’t work at all. At the end I don’t have all parents ids and my leaf_ids array is empty.

I got this output:

{
    "tree": [
        {
            "id": 1,
            "parent_id": null,
            "value": "Hi",
            "children": [
                {
                    "id": 3,
                    "parent_id": 1,
                    "value": "Hey"
                },
                {
                    "id": 4,
                    "parent_id": 1,
                    "value": "Hello"
                }
            ]
        },
        {
            "id": 2,
            "parent_id": null,
            "value": "Bye",
            "children": [
                {
                    "id": 5,
                    "parent_id": 2,
                    "value": "Cya",
                    "children": [
                        {
                            "id": 6,
                            "parent_id": 5,
                            "value": "Byebye"
                        }
                    ]
                }
            ]
        }
    ],
    "leaf_ids": [],
    "parent_ids": [
        1,
        2
    ]
}

The output that I want for leaf_ids is: "leaf_ids": [3,4,6] and for parent_ids: "parent_ids": [1,2,5].

How can I do to return leafs and parents list ?

>Solution :

When you make the recursive call, you will need to merge the results for leaf_ids and parent_ids obtained from sub tree results as well, like below:

<?php

if (isset($parentList[$item['id']])) {
    $sub_tree = makeTree($parentList, $parentList[$item['id']]);
    $item['children'] = $sub_tree['tree'];
    $leafIds = array_merge($leafIds, $sub_tree['leaf_ids']);
    $parentIds = array_merge($parentIds, $sub_tree['parent_ids']);
}

Online Demo