recursively search a multidimensional array and return all parents

[CroNiX]

Hi, I have a multidimensional array where each array has a parent id node to create a hierarchical tree.

 

$hierarchy[] = array('id' => 1, 'parent_id' => 0, 'name' = 'root1');
$hierarchy[] = array('id' => 2, 'parent_id' => 0, 'name' = 'root2');
$hierarchy[] = array('id' => 3, 'parent_id' => 1, 'name' = 'root1-1');
$hierarchy[] = array('id' => 4, 'parent_id' => 1, 'name' = 'root1-2');
$hierarchy[] = array('id' => 5, 'parent_id' => 3, 'name' = 'root1-1-1');
$hierarchy[] = array('id' => 6, 'parent_id' => 2, 'name' = 'root2-1');

 

I'm trying to come up with a recursive key/value search routine that will return all ancestor arrays of the found item without knowing the depth of the tree.  All nodes with 0 for the parent_id are root level nodes.

 

Basically I want to search for something like "where key = name and value = xxx" and have it return all ancestors of that node.

 

So if I wanted to search for "key = name and value = root1-1", it should return and array like:

array[0] = array('id' => 1, 'parent_id' => 0, 'name' = 'root1'); //parent node first
array[1] = array('id' => 3, 'parent_id' => 1, 'name' = 'root1-1');  //first child after parent

if I was to search for "key = name and value = root1-1-1", it should return:

array[0] = array('id' => 1, 'parent_id' => 0, 'name' = 'root1'); //parent node first
array[1] = array('id' => 3, 'parent_id' => 1, 'name' = 'root1-1');  //first child after parent
array[2] = array('id' => 5, 'parent_id' => 3, 'name' = 'root1-1-1'); //first grandchild

So the main problem comes in the iteration and keeping track of parents.  If I just want the array with the answer I can get that node, but I can't get it with all of the ancestors attached.  How would you go about this?  Any good ideas out there?

 

Thanks!

 

[sasa]

try

<?php
$hierarchy=array();
$hierarchy[]=array('id' => 1, 'parent_id'  => 0, 'name' => 'root1');
$hierarchy[] = array('id' => 2, 'parent_id' => 0, 'name' => 'root2');
$hierarchy[] = array('id' => 3, 'parent_id' => 1, 'name' => 'root1-1');
$hierarchy[] = array('id' => 4, 'parent_id' => 1, 'name' => 'root1-2');
$hierarchy[] = array('id' => 5, 'parent_id' => 3, 'name' => 'root1-1-1');
$hierarchy[] = array('id' => 6, 'parent_id' => 2, 'name' => 'root2-1');
function find_pat($a, $n, $key='name' ){
    $out = array();
    foreach ($a as $r){
        if ($r[$key] == $n){
            $out = find_pat($a, $r['parent_id'],'id');
            $out[]=$r;
        }
    }
    return $out;
}
$a = find_pat($hierarchy, 'root1-1-1');]
print_r($a);
?> 

[CroNiX]

try

<?php
$hierarchy=array();
$hierarchy[]=array('id' => 1, 'parent_id'  => 0, 'name' => 'root1');
$hierarchy[] = array('id' => 2, 'parent_id' => 0, 'name' => 'root2');
$hierarchy[] = array('id' => 3, 'parent_id' => 1, 'name' => 'root1-1');
$hierarchy[] = array('id' => 4, 'parent_id' => 1, 'name' => 'root1-2');
$hierarchy[] = array('id' => 5, 'parent_id' => 3, 'name' => 'root1-1-1');
$hierarchy[] = array('id' => 6, 'parent_id' => 2, 'name' => 'root2-1');
function find_pat($a, $n, $key='name' ){
    $out = array();
    foreach ($a as $r){
        if ($r[$key] == $n){
            $out = find_pat($a, $r['parent_id'],'id');
            $out[]=$r;
        }
    }
    return $out;
}
$a = find_pat($hierarchy, 'root1-1-1');]
print_r($a);
?> 

spot on!  Thank you very much!  That replaced about 60 lines of code I was using to do this manually.  I don't know why I have such a hard time wrapping my head around recursion.