PHP Nested Navigation

Question

I am building out a database-driven navigation, and I need some help in a method to build my data structure. I'm not very experienced with recursion, but that is most likely the path this will take. The database table has an id column, a parent_id column, and a label column. The result of calling the method provides me with the data structure. The way my data structure should result in the following:

• Records with a parent_id of 0 are assumed to be root elements.
• Each root element contains an array of children if a child exists which holds an array of elements containing the parent_id equal to the root element id.
• Children may contain a children array containing parent_ids equal to the immediate child (this would be the recursive point)
• When a record exists that contains a parent_id which isn't 0, it gets added to the array of the children elements.

Here is how the data structure should look:

$data = array(
  'home' => array(    
      'id' => 1,
      'parent_id' => 0,
      'label' => 'Test',
      'children' => array(
          'immediatechild' => array(
              'id' => 2,
              'parent_id' => 1,
              'label' => 'Test1',
              'children' => array(
                 'grandchild' => array(
                     'id' => 3,
                     'parent_id' => 2,
                     'label' => 'Test12',
             ))
         ))
  )

);

Here's something I came up with in a few moments. Its not correct, but its what I want to use and Id like some help fixing it.

<?php
// should i pass records and parent_id? anything else?
function buildNav($data,$parent_id=0)
{
   $finalData = array();
   // if is array than loop
   if(is_array($data)){
      foreach($data as $record){
          // not sure how/what to check here
        if(isset($record['parent_id']) && ($record['parent_id'] !== $parent_id){
            // what should i pass into the recursive call?            
            $finalData['children'][$record['label'][] = buildNav($record,$record['parent_id']);
         }
      }
    } else {
       $finalData[] = array(
        'id' => $data['id'],
        'parent_id' => $parent_id,
        'label' => $data['label'],         
     )
   } 
    return $finalData
}

Thanks for the help!

Answer 1

Simplest solution (assuming you've got the data stored in relational represenation using the parent id as a FK to indicate the hierarchy) is to just brute force it:

 $start=array(
     array('parent_id'=>0, 'title'=>'Some root level node', 'id'=>100), 
     array('parent_id'=>0, 'title'=>'Other root level node', 'id'=>193),
     array('parent_id'=>100, 'title'=>'a child node', 'id'=>83),
     ....
 );
 // NB this method will work better if you sort the list by parent id

 $tree=get_children($start, 0);

 function get_children(&$arr, $parent)
 {
    static $out_index;
    $i=0;
    $out=array();
    foreach($arr as $k=>$node) {
       if ($node['parent_id']==$parent) {
         ++$i;
         $out[$out_index+$i]=$node;
         if (count($arr)>1) {
             $out[$out_index+$i]['children']=get_children($arr, $node['id']);
         }
         unset($arr[$k]);
    }
    $out_index+=$i;
    if ($i) {
      return $out;
    } else {
      return false;
    }
 }

But a better solution is to use an adjacency list model for the data in the database. As an interim solution you might want to serialize the tree array and cache it in a file rather than parse it every time.