Tree depth recursion PHP array

Question

I have the following array and want to find the max. depth of its tree structure. But my code returns 12, when it should be 4...I am not very good at recursion, so this is kind of making me crazy!

Array Declaration:

Array (
    [relation] => Array (

        [parent.item] => Array (
                [0] => cs
                [1] => ls
            )

        [cs.item] => Array (
                [0] => business
                [1] => sporting_cultural
                [2] => tourism
                [3] => family
                [4] => friend
                [5] => student_family
                [6] => transit
                [7] => other_cases
            )

        [business.item] => Array (
                [0] => short_stay_business
                [1] => short_stay_business_tourism
                [2] => short_stay_german_company
                [3] => short_stay_german_company_tourism
                [4] => short_stay_work_training
                [5] => short_stay_work
                [6] => short_stay_student_internship
                [7] => exhibition
                [8] => scientific_research_all
            )

        [exhibition.item] => Array (
                [0] => short_stay_visitor_fair
                [1] => short_stay_visitor_fair_tourism
                [2] => short_stay_exhibitor
                [3] => short_stay_exhibitor_tourism
            )

        [scientific_research_all.item] => Array (
                [0] => short_stay_scientific_research
                [1] => short_stay_scientific_research_spouse
                [2] => short_stay_scientific_research_child
            )

        [sporting_cultural.item] => Array (
                [0] => short_stay_sporting_or_cultural
            )

        [tourism.item] => Array (
                [0] => short_stay_tourism
                [1] => medical_treatment
            )

        [medical_treatment.item] => Array (
                [0] => short_stay_medical_treatment
                [1] => short_stay_medical_treatment_tourism_friend_family_visit
                [2] => short_stay_accompanying_person_of_a_medical_patient
            )

        [friend.item] => Array (
                [0] => short_stay_friends
            )

        [family.item] => Array (
                [0] => short_stay_family
                [1] => short_stay_german_family_in_germany
                [2] => short_stay_german_family_in_china
                [3] => short_stay_non_german_family
            )

        [student_family.item] => Array (
                [0] => short_stay_student
                [1] => short_stay_entrance_exam
                [2] => short_stay_scholar_exchange
                [3] => short_stay_student_internship
            )

        [transit.item] => Array (
                [0] => transit_transit
                [1] => airport_transit_airport_transit
            )

        [other_cases.item] => Array (
                [0] => short_stay_seaman
            )

        [ls.item] => Array (
                [0] => ls_notification
            )

        [children] => Array()

    )
)

Recursion function:

function plotTree($arr, $indent=0, $mother_run=true){

    global $ini_array;
    global $depth;
    global $maxDepth;

    if ($mother_run) {
        // the beginning of plotTree. We're at rootlevel
        echo "start\n";
    }

    foreach ($arr as $key => $value) {
        if (is_array($value)) {
            foreach ($value as $subKey => $subValue) {
                if(in_array($subValue.".item", array_keys($ini_array['relation']))) {
                  $depth +=1;
                  plotTree($ini_array['relation'][$subValue.".item"],0,false);
                }
            }
            $maxDepth = $maxDepth < $depth ? $depth : $maxDepth;
        }
    }    

    if ($mother_run) {
        echo "end\n";
    }
}

[Update} I don't want to find the number of dimensions. In the example above, the tree structure follows this: parent => cs => business => exhibition

Answer 1

So I see that you're trying to measure the depth based on 'relations' in a flat array rather than actual depth of the tree.

So here's what I've been able to come up with with some explanation below:

<?php

function getMaxDepth(array $arr, array $relations = array()) {
    if (empty($relations)) {
        return array_reduce($arr, function ($result, $elem) use ($arr) {
            return max($result, getMaxDepth($elem, $arr));
        });
    }

    // Return 1 + the depth of the deepest nested tree
    return 1 + array_reduce($arr, function ($max, $elem) use ($relations) {
        // If the field is not related to another field return the current max
        if (!in_array($elem . '.item', array_keys($relations))) {
            return $max;
        }

        // Return maximum of current maximum and the depth of related tree
        return max($max, getMaxDepth($relations[$elem . '.item'], $relations));
    }, 0);
}

Use like this:

getMaxDepth($yourArray['relation']); // returns 4

So first of all, you should avoid using global or static variables, especially when dealing with recursion. Instead, we want to keep everything we need in the stack by passing it as function arguments.

The first if statement applies getMaxDepth() to each subtree separately since we want to make sure we covered all of them.

Then we simply return the depth of the deepest 'nested' tree if there is one or 0, and add one for the current element.

Hope this helps you in the future.