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.

Answer 1

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();
    }

Answer 2

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.

Answer 3

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).