Recursive tree printing

Anon

I have a database with the following fields:
cat_id TINYINT(3)
parent_id TINYINT(3)
cat_name VARCHAR(64)
The idea is that it will store a category tree for the articles section in my site. Anything whose parent_id is 0, will be assumed to be a root category (ie. top level).

This means I will need to process recursively, with some sort of reference to parent_id passing through layers of recursion.

However, I want to save on database queries and so do a "SELECT *", then use mysql_fetch_row on the results recursively, to build the tree. Does anyone have any idea how this can be done?

ie. the idea is to only have to do one db query.

So:

cat_id parent_id name
1 0 A
2 0 B
3 0 C
4 2 D
5 0 E
6 1 F
7 2 G
8 1 H
9 8 I

gives
A
|-F
+-H
+-I
B
|-D
+-G
C
E

Thanks for any help

Anon

Hi Saracen,

I am currently working on the same problem as you. I have come up with a solution, however there is a bug and it does not do only one query. But itdoes do less queries than alot of category functions I have seen.

I'll explain it here, you'll find the script below. Just a note I do have one extra field for boolean tests to find sub_categories.

First thing it does is set the result_identifier to a variable variable. You will see why later.

Then query dB to get first level of categories. Populate $output with this row's info. Then test for subcats with the child field, if no subcats then get the next record. However, if subcats exist then recall the function for another query using a different result_identifier. This where the variable variable comes in.

This set up allows the script to get all sub_cats and format them as you see fit in any order you want.

The bug I mentioned is that upon each time I go back to previous result, it continues to return records I have already retrieved. This bug is driving me nuts.

Here is the function I am using. Maybe posting it here we can get someone else in on this as well.

function build_category_tree($output="",$pid=0){
global $dbh;
static $i = 1;
$level = "level".$i;

${$level} = mysql_query("
SELECT * FROM categories
WHERE parent_id = $pid AND category_id > 0
ORDER BY name", $dbh);

do{
$output .= "${$level}<br>";

  while ($row = mysql_fetch_array(${$level})) {

	     if ($row[child] != 1) {       
        $output .= $level." | ".$row[category_id]." | " .$row[name]."<br>";                      
     }else{
	        $output .= $level." | ".$row[category_id]." | " .$row[name]."<br>";
        $i++;
        build_category_tree($output,$row[category_id]);                    

     }
  }

$i--;
if($i == 0){           
  break;               
}

}while(0);

echo $output;

}

Darin

Anon

I'm sorry, I forgot to take out a debugging line.

Where it says: $output .= "${$level}<br>";

Ignore this, it was one of a few lines I put in to show me the looping and the recursion.

Darin

Anon

Hi again Saracen,

I have the answer, I've been working on this and rewrote the function a bit and got rid of the bug. I am going to do a bit of code clean up and make it a little more portable.

By The Way, this function was designed to put the category tree into a select box but could be changed a bit to use where ever you need it.

Like I had said before, it does not reduce the queries all the way to only one. But does reduce the queries quite a bit. It only performs a query if a category has any subcats. It also does not need to do any extra queries.

I will post it here when I have cleaned it up a bit.

Darin

Anon

You may not do much better than this for the general case. Some dbms (oracle and db/2 if I recall correctly, which is not to be taken for granted in this case!) provide their own extensions to make these queries easier, but lacking that you really do have to issue one query for each sub-tree as you do here. Joe Cielko (sp?) had some columns about this a while back; perhaps they are online somewhere.

Anon

I agree the queries would be easier with other dBs if you used subqueries along with grouping and ordering. However, for the shear speed MySQL has I am trying to stay with MySQL since they are currently working on these issues. As well as MySQL is a VERY popular dB used by many people. Trying to make it as portable as possible.

I have not came up with any other ideas to reduce the number of times a new query needs to be done. Any suggestions would be appreciated and I would follow up on them.

Darin

Anon

Hi darin!

I just wanted to add my little help about this topic. I was in the same problem months ago and finally I did the recursive-multiple-select-by-category as you have done here.

However, I was very time short at the moment but later I was thinking more depper. Now, I don't have the correct one-select solution either, but I'm near of it (or so I think).

We sometimes overlooked the fact that we can join the same table twice, as in the following example:

TABLE: message
FIELDS: msg_id, parent_id

SELECT m1.msg_id, m2.msg_id
FROM message as m1, message as m2
WHERE m2.parent_id=m1.msg_id

This retrieves in one simple query the replies AND the original message id's of the replied messages (we can do another query with parent_id=0 to retrieve the unreplied messages or do a LEFT JOINT).

This is the basic idea. Of course, it has a major flaw: we can only have two levels of replies. We can elaborate this aproach by adding another field in the message (reply_level) or something like that.

I hope this helps or bring new ideas to the forum. On the other hand, I was thinking if we are pushing more time in the query side (that is, we are forcing the SQL engine). Complex table joins leads to more time consuming task, where the same results can be achieved by a few simple selects.

Jose Ruiz

Anon

I was trying to say that I don't think you can; not if you want a depth-first presentation as you sketched.

Anon

Thanks for the help guys. I had also had a similar function from before as below, which I've tidied. I like the idea about not querying unless there are subcats.

function printlist($parent_id, $parent_desc) {
$result = mysql_query("SELECT cat_name,cat_id FROM articles_cat WHERE parent_id=$parent_id") or die("ERROR");
$numres = mysql_num_rows($result);

        for($i=0;$i<$numres;$i++) {
             $section_name = mysql_result($result, $i, "cat_name");
             $section_id = mysql_result($result, $i, "cat_id");
             echo ("<option value=\"$cat_id\">$parent_desc" . "$section_name</option><br>\n");
             printlist($section_id, $parent_desc ."$section_name:");
        }
 }

Anon

Hey Jose,

I was thinking along those lines to do a join of itself but I realized as you have that it limits how many levels of categories you can get to. I even thought of using a second table to relate subcats with parent_cats. I may still go that route and just do more sorting with PHP. I think using multi-dimensional arrays may help.

Anyways, here is my function to build the tree and format for output.

function build_category_tree($output='',$pid=0){
global $dbh;
static $i = 1;
$level = "level".$i;

${$level} = mysql_query("
SELECT * FROM categories
WHERE parent_id = $pid AND category_id > 0
ORDER BY name", $dbh);

do{

 $level = "level".$i;

  while ($row = mysql_fetch_array(${$level})) {
     $indent = str_repeat("&nbsp;&nbsp;&nbsp;",$i);
     $output .= $indent.$row[name]."<br>";

     if ($row[child] = 1) {       
        $i++;
        $pid = $row[category_id];
        $level = "level".$i;            
        ${$level} = mysql_query("
                SELECT * FROM categories 
              WHERE parent_id = $pid AND category_id > 0
              ORDER BY name", $dbh);                    
        continue;
     }
  }

$i--;
if($i == 0){            
  break;               
}

}while(1);

echo $output;

}

And this is what it ouputs to the browser:

Car Audio
  Amplifiers
  Headunits
    CD Players
  Speakers
DJ Equipment
  CD Players
  Mixers
  Speakers
  Turntables
Home Audio
  Amplifiers
  CD Players
  Receivers
  Tape Players
Home Theater
  Amplifiers
  Sound Processors
  Speakers

Hope someone will be able to use this

Darin

Anon

I want to share these code with you. I use an object for retrieving data. If there is any bug please let me know. I think it is very simple,if you want to add more help yourselves 🙂

function arbol_categorias($catID,$i){
$dbsubcategorias=new ps_DB;
$q_dbsubcategorias="select * from categorias2 where parentID=$catID";
$dbsubcategorias->query($q_dbsubcategorias);
$i++;
if($dbsubcategorias->num_rows()){
while($dbsubcategorias->next_record()){
for ($n=0;$n < $i;$n++){
echo "  ";
}
echo $dbsubcategorias->f('nombre')."<br>";

				arbol_categorias($dbsubcategorias->f('categoriaID'),$i);

			}
          }
	else{
	$i--;
	echo "<br>";
	return;
	}

}