title: How do you convert a parent-child (adjacency) table to a nested set using PHP and MySQL?
body: <p>I've spent the last few hours trying to find the solution to this question online.  I've found plenty of examples on how to convert from nested set to adjacency... but few that go the other way around.  The examples I have found either don't work or use MySQL procedures.  Unfortunately, I can't use procedures for this project.  I need a pure PHP solution.</p>
  
  <p>I have a table that uses the adjacency model below:</p>
  
  <pre><code>id          parent_id         category
  1           0                 Books
  2           0                 CD's
  3           0                 Magazines
  4           1                 Books/Hardcover
  5           1                 Books/Large Format
  6           3                 Magazines/Vintage
  </code></pre>
  
  <p>And I would like to convert it to a Nested Set table below:</p>
  
  <pre><code>id    left    right          category
  0     1       14             Root Node
  1     2       7              Books
  4     3       4              Books/Hardcover
  5     5       6              Books/Large Format
  2     8       9              CD's
  3     10      13             Magazines
  6     11      12             Magazines/Vintage
  </code></pre>
  
  <p>Here is an image of what I need:</p>
  
  <p><img src="https://i.stack.imgur.com/3EFqO.png" alt="Nested Tree Chart"></p>
  
  <p>I have a function, based on the pseudo code from this forum post (<a href="http://www.sitepoint.com/forums/showthread.php?t=320444" rel="nofollow noreferrer">http://www.sitepoint.com/forums/showthread.php?t=320444</a>) but it doesn't work.  I get multiple rows that have the same value for left.  This should not happen.</p>
  
  <pre><code>&lt;?php
  
  /**
  
  --
  -- Table structure for table `adjacent_table`
  --
  
  CREATE TABLE IF NOT EXISTS `adjacent_table` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `father_id` int(11) DEFAULT NULL,
    `category` varchar(128) DEFAULT NULL,
    PRIMARY KEY (`id`)
  ) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;
  
  --
  -- Dumping data for table `adjacent_table`
  --
  
  INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
  (1, 0, 'ROOT'),
  (2, 1, 'Books'),
  (3, 1, 'CD''s'),
  (4, 1, 'Magazines'),
  (5, 2, 'Hard Cover'),
  (6, 2, 'Large Format'),
  (7, 4, 'Vintage');
  
  --
  -- Table structure for table `nested_table`
  --
  
  CREATE TABLE IF NOT EXISTS `nested_table` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `lft` int(11) DEFAULT NULL,
    `rgt` int(11) DEFAULT NULL,
    `category` varchar(128) DEFAULT NULL,
    PRIMARY KEY (`id`)
  ) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;
  
  */
  
      mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
      mysql_select_db('DATABASE') or die(mysql_error());
      adjacent_to_nested(0);
  
      /**
       * adjacent_to_nested
       *
       * Reads a "adjacent model" table and converts it to a "Nested Set" table.
       * @param   integer     $i_id           Should be the id of the "root node" in the adjacent table;
       * @param   integer     $i_left         Should only be used on recursive calls.  Holds the current value for lft
       */
      function adjacent_to_nested($i_id, $i_left = 0)
      {
  
          // the right value of this node is the left value + 1
          $i_right = $i_left + 1;
  
          // get all children of this node
          $a_children = get_source_children($i_id);
          foreach  ($a_children as $a)
          {
  
              // recursive execution of this function for each child of this node
              // $i_right is the current right value, which is incremented by the 
              // import_from_dc_link_category method
              $i_right = adjacent_to_nested($a['id'], $i_right);
  
              // insert stuff into the our new "Nested Sets" table
              $s_query = "
                  INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) 
                  VALUES(
                      NULL, 
                      '".$i_left."',
                      '".$i_right."',
                      '".mysql_real_escape_string($a['category'])."'
                  )
              ";
              if (!mysql_query($s_query))
              {
                  echo "&lt;pre&gt;$s_query&lt;/pre&gt;\n";
                  throw new Exception(mysql_error());  
              }
              echo "&lt;p&gt;$s_query&lt;/p&gt;\n";
  
              // get the newly created row id
              $i_new_nested_id = mysql_insert_id();
  
          }
  
          return $i_right + 1;
      }
  
  
  
      /**
       * get_source_children
       *
       * Examines the "adjacent" table and finds all the immediate children of a node
       * @param   integer     $i_id           The unique id for a node in the adjacent_table table
       * @return  array                       Returns an array of results or an empty array if no results.
       */
      function get_source_children($i_id)
      {
  
  
          $a_return = array();
          $s_query = "SELECT * FROM `adjacent_table` WHERE `father_id` = '".$i_id."'";
          if (!$i_result = mysql_query($s_query))
          {
              echo "&lt;pre&gt;$s_query&lt;/pre&gt;\n";
              throw new Exception(mysql_error());  
          }
          if (mysql_num_rows($i_result) &gt; 0)
          {
              while($a = mysql_fetch_assoc($i_result))
              {
                  $a_return[] = $a;
              }
          }
  
          return $a_return;
      }
  
  ?&gt;
  </code></pre>
  
  <p>This is the output of the above script.</p>
  
  <blockquote>
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '2', '5', 'Hard Cover' )</p>
    
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '2', '7', 'Large Format' )</p>
    
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '1', '8', 'Books' )</p>
    
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '1', '10', 'CD\'s' )</p>
    
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '10', '13', 'Vintage' )</p>
    
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '1', '14', 'Magazines' )</p>
    
    <p>INSERT INTO <code>nested_table</code> (<code>id</code>,
    <code>lft</code>, <code>rgt</code>, <code>category</code>) VALUES(
    NULL, '0', '15', 'ROOT' )</p>
  </blockquote>
  
  <p>As you can see, there are multiple rows sharing the lft value of "1" same goes for "2"  In a nested-set, the values for left and right must be unique.  Here is an example of how to manually number the left and right ID's in a nested set:</p>
  
  <p><img src="https://i.stack.imgur.com/rljwW.gif" alt="How to number nested sets"></p>
  
  <p>Image Credit: Gijs Van Tulder, <a href="https://www.sitepoint.com/hierarchical-data-database-2/" rel="nofollow noreferrer">ref article</a></p>