Creating a recursive category tree function

Question

I have a database with a bunch of categories, some are children:

Array
(
    [0] => Array
        (
            [id] => 1
            [name] => Home Improvement
            [slug] => Home-Improvement
            [parent] => 
            [user_id] => 1
            [order] => 1
        )

    [1] => Array
        (
            [id] => 2
            [name] => Asbestos Abatement & Removal
            [slug] => Asbestos-Abatement-Removal
            [parent] => 1
            [user_id] => 1
            [order] => 8
        )

    [2] => Array
        (
            [id] => 3
            [name] => Asphalt & Asphalt Products
            [slug] => Asphalt-Asphalt-Products
            [parent] => 1
            [user_id] => 1
            [order] => 9
        )

    [3] => Array
        (
            [id] => 4
            [name] => Bathroom
            [slug] => Bathroom
            [parent] => 1
            [user_id] => 1
            [order] => 10
        )

    [4] => Array
        (
            [id] => 5
            [name] => Kitchen Cabinets
            [slug] => Kitchen-Cabinets
            [parent] => 1
            [user_id] => 1
            [order] => 11
        )

    [5] => Array
        (
            [id] => 6
            [name] => Ceilings
            [slug] => Ceilings
            [parent] => 1
            [user_id] => 1
            [order] => 12
        )

    [6] => Array
        (
            [id] => 7
            [name] => Cleaning
            [slug] => Cleaning
            [parent] => 1
            [user_id] => 1
            [order] => 13
        )

    [7] => Array
        (
            [id] => 8
            [name] => Closet Organizers & Accessories
            [slug] => Closet-Organizers-Accessories
            [parent] => 1
            [user_id] => 1
            [order] => 14
        )

    [8] => Array
        (
            [id] => 9
            [name] => Concrete
            [slug] => Concrete
            [parent] => 1
            [user_id] => 1
            [order] => 15
        )

    [9] => Array
        (
            [id] => 10
            [name] => Contractors & Service Providers
            [slug] => Contractors-Service-Providers
            [parent] => 1
            [user_id] => 1
            [order] => 16
        )

What I'm trying to output is something like this:

<ul>
    <li>Parent
        <ul>
            <li>Child</li>
        </ul>
    </li>
    <li>Parent with no Children</li>
</ul>

I'm trying to build a recursive tree script in PHP, but I'm stuck. Here's what I have so far. I'm stuck on what to do between the else: and endif; in the foreach. (And I'm using that syntax just for easier reading here.) Any suggestions?

echo $this->categories->makeTree(0, $this->db->get('categories')->result_array());

public static function makeTree($parent, $array)
{
  if (!is_array($array)) return '';

  $output = '<ul>';

  foreach($array as $key => $value):
    if ($value['parent'] == $parent):
        $output .= '<li>';

        if ($value['parent'] == NULL):
            $output .= $value['name'];
        else:

        endif;
    endif;

    $output .= '</li>';
  endforeach;

  $output .= '</ul>';
  return $output;
}

EDIT 1

I was able to get this working, although I have a database call in a foreach loop, which probably isn't the best idea:

public function makeTree($parent, $array)
{
  if (!is_array($array)) return FALSE;

  $output = '<ul>';

  foreach($array as $key => $value):
    if ($value['parent'] == $parent):
        $output .= '<li>';

        if ($value['parent'] == NULL):
            $output .= $value['name'];

            $subcategories = ci()->db->get_where('categories', array('parent' => $value['id']));

            if ($subcategories->num_rows() > 0):
                $output .= $this->makeTree($value['id'], $subcategories->result_array());
            endif;
        else:
            $output .= $value['name'];
            $output .= '</li>';
        endif;
    endif;

  endforeach;

  $output .= '</ul>';
  return $output;
}

EDIT 2

Here is my final solution, reusing the array instead of doing a DB query:

public function makeTree($parent, $array)
{
  if (!is_array($array) OR empty($array)) return FALSE;

  $output = '<ul>';

  foreach($array as $key => $value):
    if ($value['parent'] == $parent):
        $output .= '<li>';

        if ($value['parent'] == NULL):
            $output .= $value['name'];

            $matches = array();

            foreach($array as $subkey => $subvalue):
                if ($subvalue['parent'] == $value['id']):
                    $matches[$subkey] = $subvalue;
                endif;
            endforeach;

            $output .= $this->makeTree($value['id'], $matches);

        else:
            $output .= $value['name'];
            $output .= '</li>';
        endif;
    endif;

  endforeach;

  $output .= '</ul>';

  return $output;
}

Answer 1

Though this seems answered, have a look here. With the shown function you can convert your flat data to nested data with only one iteration. Creating an ul-list from that nested data is then very easy. For example:

function nested2ul($data) {
  $result = array();

  if (sizeof($data) > 0) {
    $result[] = '<ul>';
    foreach ($data as $entry) {
      $result[] = sprintf(
        '<li>%s %s</li>',
        $entry['name'],
        nested2ul($entry['children'])
      );
    }
    $result[] = '</ul>';
  }

  return implode($result);
}

echo nested2ul(array(flat2nested( $yourFlatData ));

The good thing about this approach is that you don't have to re-iterate again and again over the input data just to find the child-elements.