Recursivly traverse simple tree in PHP

Question

I have a simple tree which takes the shape below

    ROOT
     /\
    A  B
   /    \ 
  A1     B1
          \
           B11

This is stored in a DB table CLASSES that is self referencing.

 ID |  CLASS_ID  | PARENT_ID
 ---------------------------
  1 |     ROOT   |  
  2 |     A      | ROOT
  3 |     A1     | A
  4 |     B      | ROOT
  5 |     B1     | B
  6 |     B11    | B1
 ---------------------------

and so on, this is just an example, the class_id and parent_id columns are integers but I just made them chars for this example so you get the idea.

I then have a second table CHILDREN which I want to look like this in the end,

 ID | CLASS_ID   | CHILD_CLASS_ID
 --------------------------------
  1 |     ROOT   |  A
  2 |     ROOT   |  A1
  3 |     ROOT   |  B
  4 |     ROOT   |  B1
  5 |     ROOT   |  B11
  6 |     A      |  A1
  7 |     B      |  B1
  8 |     B      |  B11
  9 |     B1     |  B11
 ---------------------------

So essentially if a class is lower than any class within its branch it is a child of all higher classes. I know this is definitely a recursion problem but I am new to PHP could really use some help. I am running mysql. I should also mention that I will be traversing backwards. So I am inserting classes at the bottom. An example would be the next class to insert would be A11, I would then need to traverse up to find all higher classes and make them parent classes of A11.

Answer 1

Do you have to do it the was you have? Its a REALLLLY bad way in my opinion. You're queries become complex, where as if you use a Adjacency List, it is simple.

Take a look at this.

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Answer 2

Hopefully I have grasped what you are trying to do. Do you have to work backwards to create the child table?

If you work from the top down you can gather all child IDs for each parent using a MySQL GROUP_CONCAT()

SELECT PARENT_ID, GROUP_CONCAT(CLASS_ID) AS CHILDREN
FROM CLASSES
GROUP BY PARENT_ID

This should return something like:

| PARENT_ID | CHILDREN      |
-----------------------------
| ROOT      | A,A1,B,B1,B11 |
| A         | A1            |
| B         | B1,B11        |
| A1        |               |
| B1        | B11           |
| B11       |               |
-----------------------------

Then you can break that up and populate your CHILDREN table?