Build Tree function using foreach pass-by-reference
Posted: Tue Jun 09, 2009 5:40 pm
I want to build a tree structure from a flat array of nodes where each node contains in 'id' and a 'parent' (containing the id of the parent). The catch is I don't want to use recursion because I want to keep the algorithm complexity sub-exponential. I had an idea to do it in O(n) complexity using references, but I am thus far stumped.
I added some debug (formatted for outputting to a browser), so just try it cutting and pasting it into a test script on a development server and you'll see what I mean (hopefully).
And just in case you don't want to cut and paste into a test script on a development server... here's the output...
As you can see, it correctly builds the tree all the way down, but ONLY for the first root level node. Children of remaining root level nodes get lost somewhere. It appears that I am losing the reference assignment $parent_node['children'] after popping out of the inner foreach and attempting to assign to $tree at the beginning of the outer loop, if that makes sense. Thanks in advance.
I added some debug (formatted for outputting to a browser), so just try it cutting and pasting it into a test script on a development server and you'll see what I mean (hopefully).
Code: Select all
function build_tree($nodes) {
$tree = array();
foreach ($nodes as &$node) {
if (empty($node['parent'])) {
$tree[$node['id']] = &$node;
} else {
foreach($nodes as &$parent_node){
if ($parent_node['id'] == $node['parent']){
if (!isset($parent_node['children'])) {
$parent_node['children'] = array();
}
$parent_node['children'][] =& $node;
// DEBUG HERE
if ($node['id'] == 8){
echo '<br>parent node when assigning node with id 8 = ';
print_r($parent_node);
}
// END DEBUG
}
}
}
// DEBUG HERE
if ($node['id'] == 7){
echo '<br><br>node with id 7 = ';
print_r($node);
}
// END DEBUG
}
return $tree;
}
$nodes = array(
array('id'=>'1'),
array('id'=>'2', 'parent'=>'1'),
array('id'=>'3', 'parent'=>'2'),
array('id'=>'4', 'parent'=>'1'),
array('id'=>'5'),
array('id'=>'6', 'parent'=>'3'),
array('id'=>'7'),
array('id'=>'8', 'parent'=>'7'),
);
echo '<pre>';
echo 'nodes = ';
print_r($nodes);
$tree = build_tree($nodes);
echo '<br><br>tree = ';
print_r($tree);
echo '</pre>';
Code: Select all
nodes = Array
(
[0] => Array
(
[id] => 1
)
[1] => Array
(
[id] => 2
[parent] => 1
)
[2] => Array
(
[id] => 3
[parent] => 2
)
[3] => Array
(
[id] => 4
[parent] => 1
)
[4] => Array
(
[id] => 5
)
[5] => Array
(
[id] => 6
[parent] => 3
)
[6] => Array
(
[id] => 7
)
[7] => Array
(
[id] => 8
[parent] => 7
)
)
node with id 7 = Array
(
[id] => 7
)
parent node when assigning node with id 8 = Array
(
[id] => 7
[children] => Array
(
[0] => Array
(
[id] => 8
[parent] => 7
)
)
)
tree = Array
(
[1] => Array
(
[id] => 1
[children] => Array
(
[0] => Array
(
[id] => 2
[parent] => 1
[children] => Array
(
[0] => Array
(
[id] => 3
[parent] => 2
)
)
)
[1] => Array
(
[id] => 4
[parent] => 1
)
)
)
[5] => Array
(
[id] => 5
)
[7] => Array
(
[id] => 7
)
)