Mind bender array tree flattening

[zorgi]

I have multidimensional (tree) array of form like this:

$a = array
(
    "t" => array("b")
    "d" => array(
                 "p" => array("b")
                 "n" => array(
                              "p" => array ( "b")
                              )
                )
    "p" => array("b")
    "n" => array(
                 "p" => array("b")
                 )
)
 

That needs converting into 2 dimensional (tree respecting) array like this:

$a = array
(
    array("t", "b"),
    array("d", "p", "b"),
    array("d", "n", "p", "b"),
    array("p", "b"),
    array("n", "p", "b")
)
 

Any ideas!? Solve this and beer and pizza is on me :)

[zorgi]

Hm maybe this should be moved to algorithms

[Markus]

I'll move it to algorithms. :)

[Markus]

*goes to drawing board*

[jkmyoung]

Looks like a depth-first search.

{
  current node = root
  current path = nothing
  PrintPath(node, path)
}
 
PrintPath(node, path){
  if no children -> print path and return
  foreach childNode on current node{
    PrintPath(childNode, path + childnode)
  }
}

path would be a dynamically expanding array. path is passed by value, not reference, so depending on your language, you may have to copy the array.

[zorgi]

Language is php. I came up with this:

[zorgi]

@jkmyoung
Thanks to your post I came up with much neater solution.

printPath($a);
 
function printPath($node, $path = array()){
    if(!is_array($node)){
        $path[] = $node;
        print_r($path);    
        return;
    }
 
    foreach($node as $key => $child_node){
        $p = $path;        
        if(is_array($child_node)){
            $p[] = $key;
            printPath($child_node, $p);
        }else{
            printPath($child_node, $p);    
        }            
    }
}
 

Thanx. Beer and pizza is on me if we ever meet :)