Recursion Help changes aren't being saved after the first and second level

Question

I am trying to turn flat mysql rows into a tree structure.

$categories = array(
            array(
                'id' => '1',
                'name' => 'root',
                'parent' => '0',
            ),  
            array(
                'id' => '2',
                'name' => 'first',
                'parent' => '1',
            ),  
            array(
                'id' => '3',
                'name' => 'first',
                'parent' => '1',
            ),  
            array(
                'id' => '4',
                'name' => 'second',
                'parent' => '3',
            ),  
        );

I am initializing all the first level nodes first then calling build_tree on each node.

    $hierarchy = array();
    // loop through and get each root node
    foreach($categories as $key => $category) {
        if ($category['parent'] == 0) {

            // initialize this root
            $hierarchy[$category['id']] = $category;
            $hierarchy[$category['id']]['children'] = array();

            // remove this from categories
            unset($categories[$key]);

            $this->build_tree($hierarchy[$category['id']], $categories);

        }   
    }   

    return $hierarchy;

}   



function build_tree(&$node, &$categories) {

    foreach ($categories as $key => $category) {

        // check if this node is the parent
        if ($node['id']  === $category['parent']) {

            $node['children'][$category['id']] = $category;
            $node['children'][$category['id']]['children'] = array();
            unset($categories[$key]);

            $this->build_tree($category, $categories);

        }   
    }   

}

THis is only returning the first and second levels of the tree.

array
  1 => 
    array
      'id' => string '1' (length=1)
      'name' => string 'root' (length=4)
      'parent' => string '0' (length=1)
      'children' => 
        array
          2 => 
            array
              'id' => string '2' (length=1)
              'name' => string 'first' (length=5)
              'parent' => string '1' (length=1)
              'children' => 
                array
                  empty
          3 => 
            array
              'id' => string '3' (length=1)
              'name' => string 'first' (length=5)
              'parent' => string '1' (length=1)
              'children' => 
                array
                  empty

Inside of build_tree when it reaches id=2 it is creating children successfully. (finding that there is one child of id=2 and appending it to 'children' correctly)

It is just not saving it! Can anyone see what I am doing wrong?? When I var_dump hierarchy it is just the first and second level never the third even though the third is being created successfully in build_tree. Any help would be very greatly appreciated. Ty.

I find when I'm writing recursive functions that it's more effective to work backwards - first write your escape case, then write the continuation cases - is this how you developed this function? — Matt, Jul 27 '12 at 14:31
I'm guessing you need to loop with references here: `foreach ($categories as $key => &$category) {`. Note the addition of an `&`. Does that fix it? — nickb, Jul 27 '12 at 14:31
@nickb no that didn't fix it, Matt there was no tact to developing it just fumbling through it for a couple hours when i finally got the first and second level i just tried to roll with it. I will try and write the escape case first, ty — dm03514, Jul 27 '12 at 14:33
See also [Managing Hierarchical Data in MySQL](http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/), [What are the Options for Storing Hierarchical Data in a Relational Database?](http://stackoverflow.com/q/4048151/), — outis, Jul 28 '12 at 00:57
[Sample code](http://sscce.org/) should be complete. The given code is missing some lines from the first method along with sample data (as a PHP array) and the method call that starts it all off. — outis, Jul 28 '12 at 01:07

ghbarratt · Accepted Answer · 2012-07-28T00:55:34.253

For the sake of performance, it is usually a good practice to consider non-recursive solutions before recursive ones. I put together a bit of code that hopefully can help you with your category tree problem:

$dbh->setAttribute(PDO::ATTR_DEFAULT_FETCH_MODE, PDO::FETCH_ASSOC);
$sth = $dbh->prepare('SELECT * FROM categories');
$sth->execute();
$categories = $sth->fetchAll();

function buildCategoryTree(&$categories)
{

    $tree = array(0=>array('children'=>array()));

    foreach($categories as &$c)
    {
        $tree[$c['id']] = &$c;
    }

    foreach($categories as &$c)
    {
        $parent_id = $c['parent'] ?: 0;
        if(!isset($tree[$parent_id])) $tree[$parent_id]['children'] = array();
        $tree[$parent_id]['children'][] = &$c;
    }

    return $tree[0]['children'];
}

$tree = buildCategoryTree($categories);

If you had the following in the database:

mysql> SELECT * FROM categories;
+----+------+--------+
| id | name | parent |
+----+------+--------+
|  1 | A    |      0 |
|  2 | B    |      0 |
|  3 | C    |      0 |
|  4 | A1   |      1 |
|  5 | A2   |      1 |
|  6 | B1   |      2 |
|  7 | B2   |      2 |
|  8 | C1   |      3 |
|  9 | A3   |      1 |
| 10 | B2i  |      7 |
| 11 | A1ii |      4 |
| 12 | A1i  |      4 |
+----+------+--------+

then the code would produce $tree as:

Recursion Help changes aren't being saved after the first and second level

1 Answers1