recursion function in php not working as expected

Question

private function find_children ($parent_id, $children, &$result)
{              
    foreach ($children as $c)
    {            
        if ($c->parent_comment_id == $parent_id)
        {                
            $result[] = $c;
            $this->find_children($c->id, $children, $result);            
        }            
    }
    return;        
}

The above function is supposed to take a starting parent id and recursively go through an array of children nodes (really just an object with a unique id and a parent id) sorting them so that each node comes directly after it's parent (see below for sample data).

But for some reason, the function doesn't execute as I expect. I have the following data for testing.

id: 1 pid: 0 (the initial parent which is not in the children array passed to func. problem?)
id: 2 pid: 1
id: 3 pid: 2
id: 4 pid: 1
id: 5 pid: 3
id: 6 pid: 5
id: 7 pid: 4
id: 8 pid: 3

and want the following array returned: 1, 4, 7, 2, 3, 8, 5, 6

But instead, I get: 1, 2, 3, 5, 6

which, while they're in the right order, a few are missing.

I have not had the need to do recursion in many years, so likely I am missing something obvious, although not so obvious to myself.

In case anyone is wondering, or if it matters, I'm trying to build a q&a commenting system where every post can have multiple replies.

Thus:

initial post 
-reply to initial post #1
--reply to reply
-reply to initial post #2
-- reply to above
--- reply to above
--reply to #2

Answer 1

I think you're looking for something like a Nested Set Tree?

Check this out:

http://www.edutech.ch/contribution/nstrees/index.php

It should do what you want.

Answer 2

When i run your function on the data you listed, i do get the order you described, but i'm not missing any items:

id: 1, pid:0
id: 2, pid:1
id: 3, pid:2
id: 5, pid:3
id: 6, pid:5
id: 8, pid:3
id: 4, pid:1
id: 7, pid:4

And this result is actually the tree structure you want, just ordered ascending by the id's. If you order your chhildren-array descending by the id's, then you actually do get the output you request:

id: 1, pid:0
id: 4, pid:1
id: 7, pid:4
id: 2, pid:1
id: 3, pid:2
id: 8, pid:3
id: 5, pid:3
id: 6, pid:5

You should make sure you get the data in descending order from your DB. For this non-DB test case, i fixed it by using the following before calling find_children():

function revCmpObjects($a, $b) { //Just a basic descending ordering by the id
   if ($a->id == $b->id) {
       return 0;
   }
   return ($a->id > $b->id) ? -1 : 1;
}
usort($children, 'revCmpObjects'); //The actual sorting