Traversing a non-binary tree i php

I'm having difficulties with the recursive calls.

I have this database with a tree structure that stores "id", "parent_id" and "name" for each element. The elements with parent_id=0 is at the root level.

Anyone able to help me traverse my tree and maybe also print it to screen?

I also wanted to do this in an effective way with minimum number of queries to mysql. Could it be dnone without recursion as well? Perhaps just select all rows from the table and then iterate through them one by one, placing each record inside an array that simulates the tree...

Well then there is the problem with traversing this array... It will need recursive calls too....... Argh.

Whats the more efficient way?

These are going to be fairly simple observations, but...

First off, as a general thing, relational databases do not behave well as graphs, which is what a tree is, because and "relationship" only gets you one level.

Secondly, since you want to traverse the entire tree, it seems, that means going through your entire data structure (several times if it's in a database).

Third you can iterate just fine (doesn't need to be recursive). We start off finding the leaf nodes (has to be the leaf nodes because you don't have a facility for children).

Starting off. Find the leaf nodes. These are the ones such that no parent_id of any other row is equal to their id. There is a writeup of how to do this kind of query in the docs of the mysql web site at http://www.mysql.com/doc/en/JOIN.html
You'll have to adapt it for your own use.

After this, just examine each element, in turn, to get its parent. If you are hitting the database, it will be a lot of repeated searches. So, depending on size, you could build your own representation within PHP.

What we need is a graphical database.

Csaba Gabor

to traverse the tree you could use depth first search or breadth first search depending on how you want it displayed. depth first uses a stack while breadth first uses a queue. im not sure if php has these structures builtin, but you could create one using an array.

if you dont know what the hell depth first search or breadth first search is, then this is probably too much trouble to learn the algorithm and create the appropriate data structures.

a better way is to use celko nested sets. it is better in terms of optimality when displaying trees, although a bit more complicated when inserting and updating. check it out

http://www.sitepoint.com/print/1105

An array IS a queue right out of the box in PHP. That is to say, if you shove elements in:
$foo = array();
$foo[6] = "Hi";
$foo[3] = "Mom";
$foo[2] = "and";
$foo[1] = "Dad";

and now iterate through the array using a foreach, you get the elements out in the order they went in. Furthermore, if you delete an element by unset (say unset($foo[3]) the remaining elements stay in their originally entered order. So this is a superset of a queue's functionality.

PHP is also thoughtful enough to provide a method for getting to the last element of a hash table (which is what an array is in PHP) by means of array_splice(...) However, this reindexes the array, which tends to suggest that one cannot claim an out of the box stack by this method (I.e. can't trivially claim O(1) speed). However, if one assumes incremental numeric indeces, then knowledge of the size of the array is sufficient for a trivial implementation.

Csaba

that's great. so now you can write your recursive function.

ok, i wasnt sure how much you knew about algorithms and data structures. this is a simple depth first function, it could be made cleaner by adding some if statements in there so that declaring a stack and pushing the root would be apart of the function, but i hope this illustrates the idea. if you want breadth first then use a queue instead of a stack