title: How to convert this MPTT array into a tree structure in PHP?
body: <p>I've got hierarchal data in the database, stored in <a href="http://www.sitepoint.com/article/hierarchical-data-database/" rel="nofollow noreferrer">Modified Preorder Tree Traversal</a> format.  I'm pulling the data in a query that looks something like "SELECT ID, <code>Left</code>, <code>Right</code>, Name, etc FROM Table ORDER BY <code>Left</code>;".  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.</p>
  
  <p>I'm having trouble getting my tree structure code to work beyond the first level, though.  Here's a minimum test case:</p>
  
  <pre><code>&lt;pre&gt;&lt;?php
  
  function projectListToTree($projects) {
      $stack = Array();
      for($x =0; $x &lt; count($projects); $x++) {
          $project = $projects[$x];
          $project['Children'] = Array();
  
          while(count($stack) &gt; 0 &amp;&amp; $stack[count($stack) - 1]['Right'] &lt; $project['Right']) {
              array_pop($stack);
          }
  
          if(count($stack) &gt; 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" =&gt; "2",
          "Left" =&gt; "2",
          "Right" =&gt; "9",
          "ParentID" =&gt; "1",
          "Name" =&gt; "Parent"
      ),
      Array(
          "ID" =&gt; "3",
          "Left" =&gt; "3",
          "Right" =&gt; "4",
          "ParentID" =&gt; "2",
          "Name" =&gt; "First Child"
      ),
      Array(
          "ID" =&gt; "4",
          "Left" =&gt; "5",
          "Right" =&gt; "8",
          "ParentID" =&gt; "2",
          "Name" =&gt; "Second Child"
      ),
      Array(
          "ID" =&gt; "5",
          "Left" =&gt; "6",
          "Right" =&gt; "7",
          "ParentID" =&gt; "4",
          "Name" =&gt; "Grand Child"
      )
  );
  
  
  $tree = projectListToTree($projects);
  echo "-----\n\n\n\n";
  var_dump($tree);
  
  ?&gt;&lt;/pre&gt;
  </code></pre>
  
  <p>And here's what I'm getting for output:</p>
  
  <pre><code>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"]=&gt;
    string(1) "2"
    ["Left"]=&gt;
    string(1) "2"
    ["Right"]=&gt;
    string(1) "9"
    ["ParentID"]=&gt;
    string(1) "1"
    ["Name"]=&gt;
    string(6) "Parent"
    ["Children"]=&gt;
    array(2) {
      [0]=&gt;
      array(6) {
        ["ID"]=&gt;
        string(1) "3"
        ["Left"]=&gt;
        string(1) "3"
        ["Right"]=&gt;
        string(1) "4"
        ["ParentID"]=&gt;
        string(1) "2"
        ["Name"]=&gt;
        string(11) "First Child"
        ["Children"]=&gt;
        array(0) {
        }
      }
      [1]=&gt;
      array(6) {
        ["ID"]=&gt;
        string(1) "4"
        ["Left"]=&gt;
        string(1) "5"
        ["Right"]=&gt;
        string(1) "8"
        ["ParentID"]=&gt;
        string(1) "2"
        ["Name"]=&gt;
        string(12) "Second Child"
        ["Children"]=&gt;
        array(0) {
        }
      }
    }
  }
  </code></pre>
  
  <p>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?</p>
  
  <p>Thanks!</p>