PHP Building Recursive Array from List

Question

I am returning a list of pages and their parent pages from a MySQL database and putting all results into an array as follows where every result is an array which includes the parent, name and id of the forum (the key of array pages is also the same as page id).

For the sake of the model and the applicaiton, there are some other parameters.

• "root pages" have a parent of 0
• there are no orphaned pages

so, the MySQL query will return this dataset.

pages=>
     [1] => array(id=>1, 
                  parent=>0, 
                  name=>Hello World)
     [2] => array(id=>1, 
                  parent=>1, 
                  name=>Child of Hello World)
     [3] => array(id=>1, 
                  parent=>0, 
                  name=>Brother of Hello World)
     [4] => array(id=>4, 
                  parent=>2, 
                  name=Grand-child of Hello World)
     [6] => array(id=>6, 
                  parent=>4, 
                  name=Great-grand-child of Hello World)

i would then like to transform the array into something that looks like this

pages=>
     [1] => id=>1, 
            name=>Hello World
            children=>

                [2] => id=>1
                       name=>Child of Hello World
                       children=>

                           [4] => 
                             id=>4
                             name=> Grand-child of Hello World)
                             children=>

                                 [6] => 
                                   id=>6
                                   name=> Great-grand-child of Hello World
                                   children= null

     [3] => array(id=>1, 
                  name=>Brother of Hello World
                  children=>null

So basically, i want to turn a linear array into a nested multidimensional array so that i can print my sitemap.

it needs to be a recursive solution. there are over 700 pages and up to 5 or 6 levels.

i only want to do 1 mysql query. not 700 so please dont give me a mysql based solution.

Solution 1

<?php

$pages = array();
$pages[1] = array('id' => 1, 'parent' => 0, 'name' => 'Hello World');
$pages[2] = array('id' => 1, 'parent' => 1, 'name' => 'Child of Hello World');
$pages[3] = array('id' => 1, 'parent' => 0, 'name' => 'Brother of Hello World');
$pages[4] = array('id' => 4, 'parent' => 2, 'name' => 'Grand-child of Hello World');
$pages[6] = array('id' => 6, 'parent' => 4, 'name' => 'Great-grand-child of Hello World');

$children = array();
foreach($pages as $key => $page){
    $parent = (int)$page['parent'];
    if(!isset($children[$parent]))
        $children[$parent] = array();
    $children[$parent][$key] = array('id' => $page['id'], 'name' => $page['name']);
}

$new_pages = recursive_append_children($children[0], $children);

function recursive_append_children($arr, $children){
    foreach($arr as $key => $page)
        if(isset($children[$key]))
            $arr[$key]['children'] = recursive_append_children($children[$key], $children);
    return $arr;
}

print_r($new_pages);

?>

Outputs:

Array
(
    [1] => Array
        (
            [id] => 1
            [name] => Hello World
            [children] => Array
                (
                    [2] => Array
                        (
                            [id] => 1
                            [name] => Child of Hello World
                            [children] => Array
                                (
                                    [4] => Array
                                        (
                                            [id] => 4
                                            [name] => Grand-child of Hello World
                                            [children] => Array
                                                (
                                                    [6] => Array
                                                        (
                                                            [id] => 6
                                                            [name] => Great-grand-child of Hello World
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

    [3] => Array
        (
            [id] => 1
            [name] => Brother of Hello World
        )
)

Solution 2

Here is a quick recursive function that builds a tree. Note that it's not great (one reason is because it doesn't get rid of items that have been already added to the tree, so each time you recurse it goes thru the entire list) - but it should work enough to get you started.

function buildTree($itemList, $parentId) {
  // return an array of items with parent = $parentId
  $result = array();
  foreach ($itemList as $item) {
    if ($item['parent'] == $parentId) {
      $newItem = $item;
      $newItem['children'] = buildTree($itemList, $newItem['id']);
      $result[] = $newItem;
    }
  }

  if (count($result) > 0) return $result;
  return null;
}

$myTree = buildTree($myArray, 0);

Comments

[Paul]

This is O(N) time complexity, since both loops can be shown to look at each element in the array exactly one time.

[j6mes]

thank you for your response. just made a few minor tweaks to adjust it to the entire data array but great answer thanks. so $children[$parent][$key] = array('id' => $page['id'], 'name' => $page['name']); is now $children[$parent][$key] = $pages[$key];

[j6mes]

thanks for helping. i didnt use this but gave me a good idea of how i would do it next time.

[Paul]

@Partydroid You're welcome. Only difference is that will keep the parent values in your resulting array, which it looks like you wanted to get rid of. You could always just unset($children[$parent][$key]['parent']); though too.

[Nic]

@Paulpro I know this is very old but I think that in the first foreach instead of $children[$parent][$key] it should be $children[$parent][$page['id']]