Find all descendants in array

At first look it was a simple task, but when I tried to solve it I became confused.

I have PHP array, where keys are top parent IDs, values are child IDs. Some child IDs have their own children. That children may have own children and so on. My goal is to get a new array, where all top parent IDs have all their descendants at all levels (children, grandchildren, great grandchildren and so on).

<?php 
// Source array 
$source = array(
    '24' => array(
        '23',
        '22'
    ),
    '25' => false,
    '22' => array(
        '21'
    ),
    '21' => array(
        '20'
    ),
    '20' => array(
        '19'
    ),
    '19' => array(
        '18'
    ),
    '18' => array(
        '17'
    )
);

// Result array I need to achieve
$result = array(
    '24' => array(
        '23',
        '22',
        '21',
        '20',
        '19',
        '18',
        '17'
    ),
    '22' => array(
        '21',
        '20',
        '19',
        '18',
        '17'
    ),
    '21' => array(
        '20',
        '19',
        '18',
        '17'
    ),
    '20' => array(
        '19',
        '18',
        '17'
    ),
    '19' => array(
        '18',
        '17'
    ),
    '18' => array(
        '17'
    )
);


?>

My attempt was next:

<?php 

function get_all_descendants($source)
{
    $result = $source;
    foreach ($source as $parent_id => $children) {
        foreach ($children as $op) {
            if (isset($source[$op])) {
                foreach ($source[$op] as $bottom_level_id) {
                    $result[$parent_id][] = $bottom_level_id;
                }
            }
        }
    }

    return $result;
}

var_dump( get_all_descendants( $source ) );

array(7) {
  [24]=>
  array(3) {
    [0]=>
    string(2) "23"
    [1]=>
    string(2) "22"
    [2]=>
    string(2) "21"
  }
  [25]=>
  bool(false)
  [22]=>
  array(2) {
    [0]=>
    string(2) "21"
    [1]=>
    string(2) "20"
  }
  [21]=>
  array(2) {
    [0]=>
    string(2) "20"
    [1]=>
    string(2) "19"
  }
  [20]=>
  array(2) {
    [0]=>
    string(2) "19"
    [1]=>
    string(2) "18"
  }
  [19]=>
  array(2) {
    [0]=>
    string(2) "18"
    [1]=>
    string(2) "17"
  }
  [18]=>
  array(1) {
    [0]=>
    string(2) "17"
  }
}

?>

But this function doesn’t find all descendants and it seems there should be recursion, but I can’t imagine how to write it. In general I have written different functions with recursion in the past, but in this case I broken my mind )

Answer

You can use a stack or recursion, then explore the structure depth-first:

<?php

function find_all_descendents($arr) {
    $all_results = [];

    foreach ($arr as $k => $v) {
        $curr_result = [];
        
        for ($stack = [$k]; count($stack);) {
            $el = array_pop($stack);

            if (array_key_exists($el, $arr) && is_array($arr[$el])) {
                foreach ($arr[$el] as $child) {
                    $curr_result []= $child;
                    $stack []= $child;
                }
            }
        }

        if (count($curr_result)) {
            $all_results[$k] = $curr_result;
        }
    }

    return $all_results;
}

$source = [
    '24' => ['23', '22'],
    '25' => false,
    '22' => ['21'],
    '21' => ['20'],
    '20' => ['19'],
    '19' => ['18'],
    '18' => ['17']
];
var_dump(find_all_descendents($source));