Q: Algorithm to create a parent-child relationship based on the order of appearance in an array I have access to an API that returns an array of product categories/sub-categories/sub-sub-categories, like this:
Array
(
    [1] => CATEGORY 1
    [2] => -Subcat 1
    [9] => -Subcat 2
    [12] => -Subcat 3
    [13] => -Subcat 4
    [46] => -Subcat 5
    [47] => -Subcat 6
    [3] => CATEGORY 2
    [4] => -Subcat 1
    [68] => -Subcat 2
    [69] => -Subcat 3
    [154] => -Subcat 4
    [5] => CATEGORY 3
    [6] => -Subcat 1
    [7] => -Subcat 2
    [76] => --Subsubcat 1
    [156] => --Subsubcat 2
    [157] => --Subsubcat 3
    [10] => -Subcat 3
    [11] => -Subcat 4
    [20] => -Subcat 5
    [54] => -Subcat 6
    [55] => -Subcat 7
    [56] => --Subsubcat 1
    [60] => --Subsubcat 2
    [65] => --Subsubcat 3
    [74] => --Subsubcat 4
    [61] => -Subcat 8
)

I'm not sure if it gets obvious, but a sub-cat (one depth symbol: -) is a direct child of the last cat (no depth symbol), and a sub-sub-cat (two depth symbols: -) is the direct child of the last sub-cat (denoted by one depth symbol -).
So, [56] => --Subsubcat 1 is the child of [55] => -Subcat 7 (its siblings are [60] => --Subsubcat 2, [65] => --Subsubcat 3, etc), whereas [55] => -Subcat 7 is the child of cat [5] => CATEGORY 3...
I know this is totally awkward, but it is what it is, and I don't have access to change it either... My problem is that I need to build from the above array a hierarchical tree of any requested id... So I'd like to build a function that will accept an $id as a param (eg 65) and will build the whole hierarchy tree, so for 65 it should return CATEGORY 3 > Subcat 7 > Subsubcat 3...
EDIT: I won't always pass a sub-sub-cat id to the function. The id could be of a sub-cat, or even a cat, and the function should return the correct hierarchy path: So for a cat, it should return that cat's name, and for a sub-cat, it should return Cat > Subcat
Can someone help me build this? Unfortunately I can't think of the proper algorithm to perform this complex task...

A: It can be solved by a simple iteration through data, keeping the categories that apply to the current element in an array:

function parents($data, $target){
    $subcats = [];
    foreach($data as $val=>$cat){
        preg_match("/^-*[^\-]/", $cat, $a);
        $level = strlen($a[0]) - 1;
        $subcats[$level] = substr($cat, $level);
        array_splice($subcats, $level+1);
        if($val == $target){
            return implode(' > ', $subcats);
        }
    }
    return "";// not found
}

$data = Array
(
    1 => "CATEGORY 1",
    2 => "-Subcat 1",
    9 => "-Subcat 2",
    12 => "-Subcat 3",
    13 => "-Subcat 4",
    46 => "-Subcat 5",
    47 => "-Subcat 6",
    3 => "CATEGORY 2",
    4 => "-Subcat 1",
    68 => "-Subcat 2",
    69 => "-Subcat 3",
    154 => "-Subcat 4",
    5 => "CATEGORY 3",
    6 => "-Subcat 1",
    7 => "-Subcat 2",
    76 => "--Subsubcat 1",
    156 => "--Subsubcat 2",
    157 => "--Subsubcat 3",
    10 => "-Subcat 3",
    11 => "-Subcat 4",
    20 => "-Subcat 5",
    54 => "-Subcat 6",
    55 => "-Subcat 7",
    56 => "--Subsubcat 1",
    60 => "--Subsubcat 2",
    65 => "--Subsubcat 3",
    74 => "--Subsubcat 4",
    61 => "-Subcat 8",
);
    
foreach([154, 65, 5, 157, 159] as $test){
    echo $test . ":" . parents($data, $test) . "\n";
}

https://onecompiler.com/php/3ynz78nwh
Edit:
The following function creates a new array with the same keys but values replaced by the full category path:
function parentsAll($data){
    $parents = Array();
    $subcats = [];
    foreach($data as $val=>$cat){
        preg_match("/^-*[^\-]/", $cat, $a);
        $level = strlen($a[0]) - 1;
        $subcats[$level] = substr($cat, $level);
        array_splice($subcats, $level+1);
        $parents[$val] = implode(' > ', $subcats);
    }
    return $parents;
}

https://onecompiler.com/php/3ynzaaard
