CODEWITHSUNDEEP
phparraysrecursiontreechildren
Karl
Karl

Reputation: 5473

Recursively obtain all children from a single parent

I have an array of folders, each have a unique ID and a parent ID. What I'm trying to do is find all of the children folders from a parent, even if a child is a sub-sub-folder, or a sub-sub-sub-folder (infinitely). All I need is an array of all of these ID's.

For example if I have the following array

$folders = [
    [
        'id' => 1,
        'parent' => null
    ],
    [
        'id' => 2,
        'parent' => null
    ],
    [
        'id' => 3,
        'parent' => 1
    ],
    [
        'id' => 4,
        'parent' => 3
    ],
    [
        'id' => 5,
        'parent' => 4
    ],
    [
        'id' => 6,
        'parent' => 1
    ]
];

If I want to get all children of folder ID 1, need to be able to loop through and get the following in response:

$children = [3,4,5,6];

I've tried the following:

public function getChildrenIds($folders, $parent_id)
{
    $folderIds = [];
    foreach($folders as $folder) {
        if($folder['parent'] == $parent_id) {
            $folderIds[] = $folder['id'];
        }
    }
    return $folderIds;
}

But my question is, how can I make this recusrive?

Upvotes: 1

Views: 880

Answers (2)

Nigel Ren
Nigel Ren

Reputation: 57131

This version does use recursion, it first arranges the array as just the id as the key and the id as the value (using array_column()).

Then as it matches each parent to the id it adds it to a list and then calls itself to add any sub children...

public function getChildrenIds($hierarchy, $parent_id)  
{
    $folderIds = [];
    foreach ( $hierarchy as $id => $folder )   {
        if ( $folder == $parent_id )    {
            $folderIds[] = $id;
            $folderIds = array_merge($folderIds, getChildrenIds($hierarchy, $id));
        }
    }

    return $folderIds;
}

Forgot to add that the array folders should be converted using...

$hierarchy = array_column($folders, 'parent', 'id');

to be passed in.

Upvotes: 1

Nigel Ren
Nigel Ren

Reputation: 57131

Rather than make it recursive, you can expand the check to check for all of the so far found parent nodes(using in_array(). This makes it a one pass check..

public function getChildrenIds($folders, $parent_id)  
{
    // Prime array with parent looking for
    $folderIds = [$parent_id];
    foreach($folders as $folder) {
        // Check if matches any parent so far found
        if( in_array($folder['parent'], $folderIds) ) {
            $folderIds[] = $folder['id'];
        }
    }

    // Remove parent id added at start
    array_shift($folderIds);
    return $folderIds;
}

Upvotes: 1

Related Questions