Mind bender array tree flattening

[zorgi]

I have multidimensiona l (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]

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.

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 :)