How to convert this MPTT array into a tree structure in PHP?

Question

I've got hierarchal data in the database, stored in Modified Preorder Tree Traversal format. I'm pulling the data in a query that looks something like "SELECT ID, Left, Right, Name, etc FROM Table ORDER BY Left;". I'm trying to convert this data from a flat array the DB gives me into a tree-structure which I will then output as JSON with PHP's json_encode function.

I'm having trouble getting my tree structure code to work beyond the first level, though. Here's a minimum test case:

<pre><?php

function projectListToTree($projects) {
    $stack = Array();
    for($x =0; $x < count($projects); $x++) {
     $project = $projects[$x];
     $project['Children'] = Array();

     while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) {
      array_pop($stack);
     }

     if(count($stack) > 0) {
      $stack[count($stack) - 1]['Children'][] = $project; 
      echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of "
       . count($stack[count($stack) - 1]['Children']) . " kids\n";
     } else {
      echo "No parent\n"; 
     }

     echo "stack count: " . count($stack) . "\n";

     array_push($stack, $project);
    }

    echo "Left in stack: " . count($stack) . "\n";

    return $stack[0];
}

/*
This is basically what comes from the DB.
Should be:
  Parent
    First Child
    Second Child
      Grand Child
*/
$projects = Array(
    Array(
     "ID" => "2",
     "Left" => "2",
     "Right" => "9",
     "ParentID" => "1",
     "Name" => "Parent"
    ),
    Array(
     "ID" => "3",
     "Left" => "3",
     "Right" => "4",
     "ParentID" => "2",
     "Name" => "First Child"
    ),
    Array(
     "ID" => "4",
     "Left" => "5",
     "Right" => "8",
     "ParentID" => "2",
     "Name" => "Second Child"
    ),
    Array(
     "ID" => "5",
     "Left" => "6",
     "Right" => "7",
     "ParentID" => "4",
     "Name" => "Grand Child"
    )
);


$tree = projectListToTree($projects);
echo "-----\n\n\n\n";
var_dump($tree);

?></pre>

And here's what I'm getting for output:

No parent
stack count: 0
Adding First Child to Parent for a total of 1 kids
stack count: 1
Adding Second Child to Parent for a total of 2 kids
stack count: 1
Adding Grand Child to Second Child for a total of 1 kids
stack count: 2
Left in stack: 3
-----



array(6) {
  ["ID"]=>
  string(1) "2"
  ["Left"]=>
  string(1) "2"
  ["Right"]=>
  string(1) "9"
  ["ParentID"]=>
  string(1) "1"
  ["Name"]=>
  string(6) "Parent"
  ["Children"]=>
  array(2) {
    [0]=>
    array(6) {
      ["ID"]=>
      string(1) "3"
      ["Left"]=>
      string(1) "3"
      ["Right"]=>
      string(1) "4"
      ["ParentID"]=>
      string(1) "2"
      ["Name"]=>
      string(11) "First Child"
      ["Children"]=>
      array(0) {
      }
    }
    [1]=>
    array(6) {
      ["ID"]=>
      string(1) "4"
      ["Left"]=>
      string(1) "5"
      ["Right"]=>
      string(1) "8"
      ["ParentID"]=>
      string(1) "2"
      ["Name"]=>
      string(12) "Second Child"
      ["Children"]=>
      array(0) {
      }
    }
  }
}

As you can see, somewhere "Grandchild" is getting lost, even though the output in the projectListToTree function seems to indicate it should be there. It seems like any tree structure I throw at it drops anything below the second level. Any insight into what might be happening?

Thanks!

Answer 1

The problem is that assigning an array does not copy references, but makes a copy of the array. This means, that the "Second Child" array you have in "children" of the "Parent" node is not the same array that you add "Grandchild" to, but a copy of it.

To resolve the issue, you have to explicitly use reference assignment instead of copying:

function projectListToTree($projects) {
    $stack = Array();
    for($x =0; $x < count($projects); $x++) {
        $project = &$projects[$x];
        $project['Children'] = array();

        while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) {
                array_pop($stack);
        }

        if(count($stack) > 0) {
                $stack[count($stack) - 1]['Children'][] = &$project; 

                echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of "
                        . count($stack[count($stack) - 1]['Children']) . " kids\n";

                echo "\n";
        } else {
                echo "No parent\n"; 
        }

        echo "stack count: " . count($stack) . "\n";

        $stack[] = &$project;
    }

    echo "Left in stack: " . count($stack) . "\n";

    return $stack[0];
}

Note, that an ampersand was added at three places.

Because of this issue, one has to be extremely careful when using nested arrays and assignment operators in php.

This also means that processor usage and memory footprint is intensive when using lots of data in nested arrays. For example, in the above example, when projectListToTree() returns, the complete array tree is copied to the local variable $tree and (since the php garbage collector sucks) is in memory twice.

Answer 2

Have you put an echo statement in to see when you're calling array_pop()? From reading this without testing, I think you're popping the record off the stack and throwing it away.

Answer 3

Guys, can anyone point me to a reference / explanation of what the algorithm m is to go form flat -> hierachical. I've been playing with this sample for a couple of hours and it's not working on my data.