在数组中反向递归以查找父ID

Question

Trying to figure out a way of getting the parent ID of an item in a multi dimensional array:

$Arr = array(
    array(
        "Id" => 1,
        "Parent" => 0,
        "Children" => array(
            array(
                "Id" => 2,
                "Parent" => 1,
                "Children" => array(),
            ),
            array(
                "Id" => 3,
                "Parent" => 1,
                "Children" => array(
                    array(
                        "Id" => 4,
                        "Parent" => 3,
                        "Children" => array(),
                    ),  
                ),
            ),
        ),
    ), 
    array(
        "Id" => 5,
        "Parent" => 0,
        "Children" => array(
            array(
                "Id" => 6,
                "Parent" => 5,
                "Children" => array(),
            ),
        ),
    )
);

I need to get the "Id" for the top element where "Parent" = 0. I.e. for the item with Id 4 it should return 1 as result, or a search for 6 would return 5. I have tried various ways of recursive function but only manage to get the correct result when the depth is 2.

I have found this function but it seems to return the name of the key rather than the value:

function find_parent($array, $needle, $parent = null) {
    foreach ($array as $key => $value) {

        if (is_array($value)) {
            $pass = $parent;
            if (is_string($key)) {
                $pass = $key;
            }
            $found = find_parent($value, $needle, $pass);
            if ($found !== false) {
                return $found;
            }
        } else if ($key === 'Id' && $value === $needle) {
            return $parent;
        }
    }

    return false;
}

Edit

The following only works on the 1st level/depth:

function GetParent($Data = array(), $Needle = 0){
    foreach($Data as $Key => $Item){
        if($Item['Id'] === $Needle && $Item['Parent'] == 0){
            return $Item['Id'];             
        }
        if(sizeof($Item['Children']) !== 0)
            GetParent($Item['Children'], $Item['Parent']);

    }
    return false;
}

I don't understand what I'm doing wrong.

Answer 1

While it is not usually speed efficient, but PHP has a really great feature in the Standard PHP Library (SPL) called Iterators. Anong them you can find RecursiveArrayIterator which saves you from writing the recursive functions for yourself. In you case, you have to redefine two of its methods:

class CustomRecursiveIterator extends RecursiveArrayIterator
{
    public function hasChildren() {
        return !empty($this->current()['Children']) && is_array($this->current()['Children']);
    }

    public function getChildren()
    {
        return new static($this->current()['Children']);
    }
}

Doing so, you can be sure that you will loop over children, but not all array elements.

Given this class you can write function that will suit your needs:

function getParentId($id, array $array)
{
    $iterator = new RecursiveIteratorIterator(
        new CustomRecursiveIterator($array),
        RecursiveIteratorIterator::CHILD_FIRST 
    );

    $childFound = false;
    foreach ($iterator as $item) {
        if (
            $childFound
            && isset($item['Parent'])
            && $item['Parent'] === 0
            && isset($item['Id'])
        ) {
            return $item['Id'];
        }

        if (isset($item['Id']) && $item['Id'] === $id) {
            $childFound = true;
        }
    }

    return null;
}

Pay attention to this flag RecursiveIteratorIterator::CHILD_FIRST.

Be aware that this implementation will not work if your array structure is invalid. For example, if there is a child with given id, but it doesn't have an ancestor with zero-parent, it will return the next element with zero-parent.

Here is working demo.