Getting a list of children from an array with Parents, without recursion in PHP

Question

I have a situation where I have already obtained and manipulated SQL data into an array and into a tree. I am trying to avoid recursion at all costs because it has bitten me in the behind in the past.

I have an array of elements with Parent_IDs, and I'd like to be able to obtain a list of all of their children and subchildren. It shouldnt be nearly as complex as going the other way (from an array to a nested tree) which I got without issue using references, but for some reason I'm brain-frozen...

Any help appreciated.

I have the data in two possible formats because I have manipulated it already. Whichver is best for input can be used. this is a structure (print_r) of the two arrays I have:

Array
(
    [202735] => Array
        (
            [ID] => 202735
            [text] => aaafdf
            [Parent] => 
        )

    [202737] => Array
        (
            [ID] => 202737
            [text] => Filho 2
            [Parent] => 202735
        )

    [202733] => Array
        (
            [ID] => 202733
            [text] => Neto 1
            [Parent] => 202731
        )

    [202739] => Array
        (
            [ID] => 202739
            [text] => Neto 2
            [Parent] => 202737
        )

)

or

Array
(
    [0] => Array
        (
            [ID] => 202735
            [text] => aaafdf
            [Parent] => 
            [children] => Array
                (
                    [0] => Array
                        (
                            [ID] => 202737
                            [text] => Filho 2
                            [Parent] => 202735
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [ID] => 202739
                                            [text] => Neto 2
                                            [Parent] => 202737
                                        )

                                )

                        )

                )

        )

    [1] => Array
        (
            [ID] => 202733
            [text] => Neto 1
            [Parent] => 202731
        )

)

Desired output in the format: (first level parent => all children and grandchildren)

array(202731=>array(202735));
array(202735=>array(202737,202739));

or similar... Ideally i'll wrap this in a function like ListChildren($InitialParent), and return all children from such... invoking ListChildren(0) or (null) would list all elements and all subs...

(additional array elements can be ignored for the purpose of this exercise)

OBS: some data in the array is missing... namely the category above 202735, which would be 202731, but thats just because i limited the data I copied in... basically I can have either a flat array with parent ids, or a "tree" array with nested children as the source.

RVN · Accepted Answer · 2012-04-04 13:05:07Z

2

I ended up with this. Thanks for the help, in the end I reverted to a recursive code. I'll monitor it for performance although I suppose just within the PHP layer it wont be an issue. I had a bad experience when I went in for maintenance on a project that had DB calls in a recursive function... as the usage grew the recursvie function usage grew exponentially and the DB calls went to 100s of thousands...

anyways:

    function __GetChildrenRec($Lista, $Categoria){
        // Return false if $initialParent doesn't exist
        if ($Categoria == 0) $Categoria = "";
        if (!isset($Lista[$Categoria])) return FALSE;

        // Loop data and assign children by reference
        foreach ($Lista as $CategAtual) {
            if ($CategAtual[Parent] == $Categoria) {
                $Filhos[] = $CategAtual[ID];
                $Filhos = array_merge((array)$Filhos,(array)self::__GetChildrenRec($Lista, $CategAtual[ID]));
            }
        }

        // Return the data
        return is_array($Filhos) ? $Filhos : array();
    }

answered Apr 4, 2012 at 13:05

RVN

831 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Andrew Kozak Over a year ago

Congrats on the fix! When you are able, please make sure to mark your answer as 'accepted' so that others may learn from your success. Cheers~

RVN Over a year ago

Thks... I tried but need to wait until tomorrow to do that... Will do it tomorrow...

GordonM · Accepted Answer · 2012-04-03 15:42:28Z

0

There really is no reason to avoid recursion unless it is causing you a genuine performance problem. Recursion is how most developers looking at problems of this nature would probably attempt to solve them, and using alternative approaches can hurt maintainability because your code is doing something that someone who needs to maintain your code at a later date doesn't expect.

Generally speaking, unrolling recursion means managing a stack. Recursion is a way of getting the language you're using to manage the stack for you, if you don't use recursion, then you'll need to manipulate a stack yourself inside your function. The simplest way of doing this is with array_push and array_pop, functions built into PHP that let you use an array as a stack.

The stack-based approach is rather complex compared to simply using recursion though, and if recursion is giving you problems then manually maintaining a stack certainly will. There are benefits to be sure, but honestly I'd suggest that you try to figure out recursion instead, as it really is easier to deal with, and while it isn't as performant as managing a stack yourself, the performance loss in probably not going to be a bottleneck in your code as the bottlenecks in PHP scripts tend to be where PHP interfaces with the outside world (databases, files, network connections, etc).

answered Apr 3, 2012 at 15:42

GordonM

31.9k17 gold badges94 silver badges134 bronze badges

2 Comments

DaveRandom Over a year ago

...except that this problem can easily be solved with references. Although it is true that there is no good reason to avoid recursion in general.

GordonM Over a year ago

Yeah, good point. Didn't think of that until I saw the other answer.

DaveRandom · Accepted Answer · 2012-04-03 15:49:08Z

0

Using the first array format:

function list_children ($array, $initialParent) {

  // Return false if $initialParent doesn't exist
  if (!isset($array[$initialParent])) return FALSE;

  // Loop data and assign children by reference
  foreach ($array as &$item) {
    if (isset($array[$item['parent']])) {
      if (!isset($array[$item['parent']]['children'])) $array[$item['parent']]['children'] = array();
      $array[$item['parent']]['children'][] = &$item;
    }
  }

  // Return the data
  return (isset($array[$initialParent]['children'])) ? $array[$initialParent]['children'] : array();

}

What this does is basically create the second array from the first, but it does it by reference - so the initial parent can still be found by it's ID, and returned. Returns the array of children, an empty array() if there are no children, or FALSE if the $initialParent doesn't exist.

edited Apr 3, 2012 at 15:49

answered Apr 3, 2012 at 15:42

DaveRandom

88.8k11 gold badges159 silver badges174 bronze badges

3 Comments

RVN Over a year ago

This kind of works but leaves me no further than I was before, as it isnt outputting a "flat" array... its a nested array very very similar to my second array example... thanks for the effort though :/

DaveRandom Over a year ago

How do you want to flatten the array? You mean you just want a 1D array of the id's of all the children of a given parent? That is more or less impossible without recursion...

RVN Over a year ago

Yes, one array with all children and grandchildren... I guess thats why my brain was crapping out... lol... more-or-less impossible settles it for me then, I'll do a little recursive one then... I guess since the DB call is out of recursion it shouldnt be an issue. thanks anyways

Collectives™ on Stack Overflow

Getting a list of children from an array with Parents, without recursion in PHP

3 Answers 3

2 Comments

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related