Retrieve Child Objects

Question

I want a table of comments like so

id | comment | parent_id
--------------------------
1    text1        0
2    text2        1
3    text3        2
4    text4        3
5    text5        3
6    text6        5

I want to construct an array displaying the hierarchy of the parents and children. The tree should go back a undetermined number of generations. I don't want to use nesting foreach loops as I'm not sure how deep it goes. That is why I'm here, I'm not sure of the best practice for a problem like this. I also want to display the depth in the array. Below is an example. It doesn't really relate to table above, but hopefully gives you an idea of what I need.

array(
    "depth"=> 4
    "parent" => array(
        "id"=> 1,
        "comment" => "sometext1"
        "child_count" => 2,
        "children" => array(
            0 => array(
                "id" => 2
                "comment" => "sometext2",
                "child_count" => 0,
                "children" => null
            ),
            1 => array(
                "id" => 3
                "comment" => "sometext3"
                "child_count" => 1,
                "children" => array(
                    0 => array(
                        "id" => 2
                        "comment" => "sometext2",
                        "child_count" => 2,
                        "children" => array(
                            0 => array(
                                "id" => 2
                                "comment" => "sometext2",
                                "child_count" => 0,
                                "children" => null
                            ),
                            1 => array(
                                "id" => 2
                                "comment" => "sometext2",
                                "child_count" => 1,
                                "children" => array(
                                    "id" => 2
                                    "comment" => "sometext2",
                                    "child_count" => 0,
                                    "children" => null
                                )
                            )
                    )
                )
            )
        )
    )
)

I was going to use foreach and do a SQL statement to retrive that parent/childs children. ie

$sql = "SELECT * FROM comments WHERE parent = $parent_id";

Im not really looking for the code for all this, just a pseudo code solution.

Please take a look at my answer, I have provided a super-simple way to do this on PHP. which actually works very good. — , Sep 02 '11 at 15:11
you are awesome. Thanks. I do appreciate @Layke method, but may take me a bit to get my head round it. In the meantime I will accept your answer. — madphp, Sep 02 '11 at 16:07

score 1 · Answer 1 · edited May 23 '17 at 12:12

This is the problem when you use Adjacency list for trying to retrieve all child nodes in the hierarchy. It just doesn'y handle recursion very well if you are using mysql. (Oracle is another matter).

Creating the structure is simple, you should not really concern yourself with how to create the array structure just yet, first you want to try and create an efficient query and effiecient models that play perfectly to the type of queries that you will be making.

For example, you say that you want to retrieve all child nodes. Well then you should probably be using nested set models instead or in addition to adjacency list.

Take a look at some of these resources...

Is there a simple way to query the children of a node?

The idea of a nested set, is that you store the lft and right edge values of a node, meaning that retrieving any child nodes, is incredibly simple, beause you just select nodes which have a lft value greater than the target nodes lft value, and smaller than the rgt value.

Once you retrieve your result set, creating your array structure will be effortless.

See here : http://en.wikipedia.org/wiki/Nested_set_model

Once you have your results, then take a look at this question, which I asked a year or so ago, which is exactly what you want. PHP > Form a multi-dimensional array from a nested set model flat array

Example

id | comment | parent_id  |   lft    |    rgt   |
-------------------------------------------------
1    World        null         1           12
2    Europe        1            2           11
3    England       2            3           10
4    Kent          3            4           5
5    Devon         3            6           9
6    Plymouth      5            7           8

Thanks Layke. For the Nested Set Model question answer you linked first. Can you give me an example of the schema for that solution. Trying to wrap my head around it. — madphp, Sep 02 '11 at 14:56

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

This can be easily done in PHP... For this you need two arrays and a two while loops.

This code will make a tree the way you wanted and for an undetermined depth and number of children.

Pastebin to the working code.

Using references, lets imagine everything is saved in an array $data with this structure: (id, comment, parent_id) where parent_id points to an id.

Code to build the tree.

$tree = array();
reset($data);
while (list($k, $v) = each($data))
    if (0 == ($pid = $v['parent_id']))
        $tree[$k] =& $data[$k]; else
        $data[$pid]['children'][$k] =& $data[$k];

And to generate the depth and child count.

reset($data);
while (list($k, $v) = each($data))
    if (0 != $v['parent_id'])
    {
        $ref =& $data[$k];
        $depth = 0;
        do
        {
            if ($depth) $ref =& $data[$ref['parent_id']];
            $dre =& $ref['depth'];
            if (!isset($dre) || $dre <= $depth) $dre =  $depth++;
            if (isset($ref['children']))
                $ref['child_count'] = count($ref['children']);
                else
            {   
                $ref['child_count'] = 0;
                $ref['children'] = null;
            }   
        }   
        while ($ref['parent_id']);
    }

~~All my code has been written on the fly and not even tested, so if there are any errors please forgive meeeeeeeee!!!!!!!!!!!~~ ← Forget that, I tried it, fixed a couple of issues and now works perfectly.

Note

For this code to work, the index of every item has to be equal to its ID.

The array I used to try the code.

$data = array(
    '1' => array('id' => '1', 'comment' => 'a', 'parent_id' => 0),
    '2' => array('id' => '2', 'comment' => 'b', 'parent_id' => 0),
    '3' => array('id' => '3', 'comment' => 'c', 'parent_id' => 1),
    '4' => array('id' => '4', 'comment' => 'd', 'parent_id' => 1),
    '5' => array('id' => '5', 'comment' => 'e', 'parent_id' => 2),
    '6' => array('id' => '6', 'comment' => 'f', 'parent_id' => 2),
    '7' => array('id' => '7', 'comment' => 'g', 'parent_id' => 5),
    '8' => array('id' => '8', 'comment' => 'h', 'parent_id' => 7)
    );

what was the reason/necessity to have the key manually created. ie array('1'=> array('id' ? — madphp, Sep 02 '11 at 17:57
Because if they don’t match, references I do when climbing up the branches would refer to the ID of the parent less one. Apart from being wrong, they might easily fall in unlimited iterations which would freeze the script. — , Sep 02 '11 at 18:19
Open a new question about this and I will answer to it if nobody does first. ;) — , Sep 02 '11 at 18:48
http://stackoverflow.com/questions/7288081/traverse-array-and-display-in-bullet-points — madphp, Sep 02 '11 at 19:00

Retrieve Child Objects

2 Answers2

Example

Note