Adjacency tree from single table

Question

I've read a lot of people discussing nested lists, but I was wondering how to iterate through an adjacancy list/tree in PHP.

I have a table with: id, title, parent_id

And I've selected all records out into an array called $pages.

Then using this php:

function makeList($pages, $used) {
    if (count($pages)) {
        echo "<ul>";
        foreach ($pages as $page) {
            echo "<li>".$page['pag_title'];
            $par_id = $page['pag_id'];
            $subsql("SELECT * FROM pages WHERE pag_parent = ".$par_id."");

            // running the new sql through an abstraction layer
            $childpages = $dbch->fetchAll();
            makeList($childpages, $used, $lastused);
            echo "</li>";
        }
        echo "</ul>";
    }
}

This sort of works but I end up with any sub menu being repeated e.g.

• Home
  • News
    • Sub-news
  • Articles
    • Article
• News
  • Sub-news
• Articles
  • Article
• Sub-news
• Article

I've tried adding the current id into an array that gets passed through the function, and then using in_array to check if it's there, but I have had no joy doing that.

Any help would be much appreciated.

I need to parse the whole tree so choosing parent as 0 isn't an option

Answer 1

The simplest fix would just be, when you are doing the initial select to set $pages (which you don't show), add a WHERE clause like:

WHERE pag_parent = 0

(or IS NULL, depending how you're storing "top level" pages).

That way you won't select all the children initially.

Answer 2

Where is $page coming from? You might have an sql injection vulnerability in your code if you're not escaping it or using a prepared statement.

Also the SELECT statement inside a for loop jumps out as a bad practice. If the table is not that big, then select the contents of the entire table and then iterate through the result set in PHP to build the tree data structure. This could take up to n*(n-1)/2 iterations in the pathological case of your tree being a linked list. Stop when all nodes have been added to the tree, or the number of remaining nodes remains the same from one iteration to the next - this means the remaining nodes are not children of your root node.

Alternatively, if your database supports recursive SQL queries, you can use that, and it will only select the nodes that are children of your parent node. You will still have to build the tree object yourself in PHP. The form of the query would be something like:

WITH temptable(id, title, parent_id) AS (
  SELECT id, title, parent_id FROM pages WHERE id = ?
  UNION ALL
  SELECT a.id, a.title, a.parent_id FROM pages a, temptable t
   WHERE t.parent_id = a.id
) SELECT * FROM temptable

Substitute the '?' on the second line with the starting page ID.

Answer 3

Since it already does the SQL, you dont have to do it outside before the first function call.

function makeList($par_id = 0) {
    //your sql code here
    $subsql("SELECT * FROM pages WHERE pag_parent = $par_id");
    $pages = $dbch->fetchAll();

    if (count($pages)) {
        echo '<ul>';
        foreach ($pages as $page) {
            echo '<li>', $page['pag_title'];
      makeList($page['pag_id']);
      echo '</li>';
        }
        echo '</ul>';
    }
}

For storing it more tree like you might want to look at this site: Storing Hierarchical Data in a Database.

Answer 4

If you create an array of pages grouped by parent id it is quite easy to recursively build the list. This will only require one database query.

<?php

 //example data
 $items = array(
    array('id'=>1, 'title'=>'Home', 'parent_id'=>0),
    array('id'=>2, 'title'=>'News', 'parent_id'=>1),
    array('id'=>3, 'title'=>'Sub News', 'parent_id'=>2),
    array('id'=>4, 'title'=>'Articles', 'parent_id'=>0),
    array('id'=>5, 'title'=>'Article', 'parent_id'=>4),
    array('id'=>6, 'title'=>'Article2', 'parent_id'=>4)
 );

 //create new list grouped by parent id
 $itemsByParent = array();
 foreach ($items as $item) {
    if (!isset($itemsByParent[$item['parent_id']])) {
        $itemsByParent[$item['parent_id']] = array();
    }

    $itemsByParent[$item['parent_id']][] = $item;
 }

 //print list recursively 
 function printList($items, $parentId = 0) {
    echo '<ul>';
    foreach ($items[$parentId] as $item) {
        echo '<li>';
        echo $item['title'];
        $curId = $item['id'];
        //if there are children
        if (!empty($items[$curId])) {
            makeList($items, $curId);
        }           
        echo '</li>';
    }
    echo '</ul>';
 }

printList($itemsByParent);

Answer 5

When that table gets large, recursion can get unwieldy. I wrote an blog post about a recursion-less method: http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/