multi level menu programming output issue

Question

I'm trying to make a multi level menu in php, but I can't output the html correctly.

Firstly I extract the data from db sort it after 'sort_id' and 'id' and store it in to an array.

DB structure:

id | parent_id | sort_id | title
---------------------------------
1  |     0     |    0    | test1
2  |     1     |    1    | test2
3  |     1     |    0    | test3
4  |     0     |    1    | test4
5  |     2     |    0    | test5

PHP code

function hasChildren( $id, $data ) {
  foreach  ($data as $d ) {
    if ( $d['parent_id'] == $id ) {
        return true;
        break;
    }
  }
}

function menu ($arr) {
  foreach ( $arr as $d ) {
    if( is_array($d) && $d['parent_id'] == 0 ) {
        echo "<li><a href={$d['link']}>{$d['title']}</a>";
        if ( hasChildren ($d['id'], $arr) ) echo "<ul>";
    }

    foreach ( $arr as $row ) {
       if ( is_array($row) ) {

            if( $row['parent_id'] == $d['id'] ) {
                if ( hasChildren ($row['id'], $arr) ) {
                    echo "<li><a href={$row['link']}>{$row['title']}</a><ul>";
                } else echo "<li><a href={$row['link']}>{$row['title']}</a>";

                menu($row);

                if ( hasChildren ($row['id'], $arr) ) {
                    echo "</ul></li>";
                } else echo "</li>";
            }
        }
    }
    if ( is_array($d) && $d['parent_id'] == '0' ) {
        if ( hasChildren ($d['id'], $arr) ) echo "</ul>";
        echo "</li>";
    }
  }
}

HTML output

<li>
   <a href="http://localhost">test1</a>
   <ul>
      <li><a href="http://localhost/2">test3</a></li>
      <li><a href="http://localhost/1">test2</a>
      <ul></ul>
      </li>
   </ul>
</li>
<li><a href="http://localhost/5">test5</a></li>
<li><a href="http://localhost/4">test4</a></li>

after 'test2' is opening and closing an 'ul' tag

'test5' should be a child of 'test2' and not a parent

I know this might not be the best way to do it, but anyone can tell me what I'm doing wrong?

Answer 1

1) menu($row); is useless, because it does nothing

2) if you want to apply recursion, you must write like this:

function menu($arr, $parent) {
    $open = 0;
    foreach ($arr as $row) {
        if ($parent == $row['parent_id']) {
            echo ($open?'':'<ul>')."<li><a href={$row['link']}>{$row['title']}</a>";
            menu($arr, $row['id']);
            echo "</li>";
            $open++;
        }
    }
    if ($open) {
        echo "</ul>";
    }
}

menu($array, 0);

Answer 2

If you can change your database table I would highly recommend storing your data using MPTT (modified preorder tree traversal). It solves a lot of problems** and this is a really good example: http://www.sitepoint.com/hierarchical-data-database-2/

The CakePHP guys use MPTT combined with a parent_id field.

Assuming you can't or don't want to change your database, I would use PHP to preorder the data so that children are in the array after their parent and then output the menu. I started with some test code with uasort, but the logic quickly gets messy.

Accept the answer if you're going with MPTT or add a comment if you need some help with the second solution.

** - node depth, path to node, whole tree are easy to derive and code exists to do this already.