Order flat structure into tree knowing only parents

Question

Given the following structure of arrays:

array(
   55 => array(
       'ident' => 'test 1',
       'depth' => 1,
   ),
   77 => array(
       'parent_id' => 55,
       'ident' => 'test 2',
       'depth' => 2,
   )
);

Is there a general algorithm that can be used to turn that into a nested tree?

i.e.

array(
   55 => array(
       'ident' => 'test 1',
       'depth' => 1,
       'children' => array(
            77 => array(
                'parent_id' => 55,
                'ident' => 'test 2',
                'depth' => 2,
           )
       )
   )
);

The example i have provided is simplified, the real case includes hundreds of nodes + a depth of up to 15.

What have you tried? I'd use this as a starting point: http://stackoverflow.com/questions/3975585/search-for-a-key-in-an-array-recursivly — Sergiu Paraschiv, Oct 11 '13 at 15:31
There are a lot of these sort of questions on the site, try looking for "php construct hierarchical" or something like that, eg: http://stackoverflow.com/questions/1060955/easiest-way-to-build-a-tree-from-a-list-of-ancestors/1060993#1060993 — Orbling, Oct 11 '13 at 15:32
@SergiuParaschiv just to note; what you linked to has a horrible complexity (at least when it's also feasible in O(n) => see my answer below) — bwoebi, Oct 11 '13 at 15:46
I'd argue that you first have to try it to know this issue exists, don't you think? A recursive solution is perfectly acceptable for "hundreds of nodes". — Sergiu Paraschiv, Oct 11 '13 at 15:54
@SergiuParaschiv recursively is actually `O(n^2)` Imagine 700 nodes… recursively _"only"_ ±250k iterations (in average) [plus the fact that function calls are also relatively slow generally] or just 700 iterations in total for foreach with references… I think at this point it begins to make a significant difference. — bwoebi, Oct 11 '13 at 15:58

bwoebi · Accepted Answer · 2013-10-11T15:37:12.913

4

Working with references helps a lot. This way you can still append to the children even if they're already inserted.

foreach ($array as $key => &$sub) {
    if (isset($sub['parent_id'])) {
        $array[$sub['parent_id']]['children'][$key] = &$sub;
    }
}
unset($sub); // unset the reference to make sure to not overwrite it later...

// now remove the entries with parents
foreach ($array as $key => $sub) {
    if (isset($sub['parent_id'])) { 
        unset($array[$key]);
    }
}

Some demo for this: http://3v4l.org/D6l6U#v500

edited Oct 11 '13 at 15:37

answered Oct 11 '13 at 15:26

bwoebi

23,637
5
58
79

I'm probably the only one who would prefer to avoid PHP references like the plague.. never the less, Interesting answer. – MackieeE Oct 11 '13 at 15:32
1

@MackieeE Hell, references are awesome. Without them, half of recursive stuff would be impossible. – sybear Oct 11 '13 at 15:33
2

@MackieeE yeah; I'd also try to avoid them, but that is actually a very valid use case. Because I just cannot imagine other solutions which would run in O(n) and use no references… – bwoebi Oct 11 '13 at 15:34
1

@MackieeE: I think most people hate references in PHP - can cause a hell of a mess. But bwoebi is right about the performance, without them either the memory or the processing time would fly upwards, having to store paths, etc. – Orbling Oct 11 '13 at 15:36
Interesting, I'll have a play with them tonight =] thank you, insightful! I suppose it's the fact that I feel most referencing in PHP feels very, behind the scenes, reading it initially doesn't seem to click straight away - besides +1 on the answer & demo! – MackieeE Oct 11 '13 at 17:21

Order flat structure into tree knowing only parents

1 Answers1