Recursive function for generating a multidimensional array from a database result

Question

I want to write a function that takes an array of pages / categories (from the result of a flat database) and generates an array of nested page / category elements based on the identifiers of the parent elements. I would like to do this recursively so that any level of nesting can be done.

For example: I retrieve all the pages in one query, and it looks like the database table

+-------+---------------+---------------------------+ | id | parent_id | title | +-------+---------------+---------------------------+ | 1 | 0 | Parent Page | | 2 | 1 | Sub Page | | 3 | 2 | Sub Sub Page | | 4 | 0 | Another Parent Page | +-------+---------------+---------------------------+ 

And this is the array that I would like to process in my view files:

 Array ( [0] => Array ( [id] => 1 [parent_id] => 0 [title] => Parent Page [children] => Array ( [0] => Array ( [id] => 2 [parent_id] => 1 [title] => Sub Page [children] => Array ( [0] => Array ( [id] => 3 [parent_id] => 1 [title] => Sub Sub Page ) ) ) ) ) [1] => Array ( [id] => 4 [parent_id] => 0 [title] => Another Parent Page ) ) 

I looked and tried almost all the solutions that I came across (there are a lot of them here in Stack Overflow, but it was not lucky to get something in common that would work for both pages and categories.

Here is the closest I got, but it does not work, because I assign children to the parent level of the first level.

 function page_walk($array, $parent_id = FALSE) { $organized_pages = array(); $children = array(); foreach($array as $index => $page) { if ( $page['parent_id'] == 0) // No, just spit it out and you're done { $organized_pages[$index] = $page; } else // If it does, { $organized_pages[$parent_id]['children'][$page['id']] = $this->page_walk($page, $parent_id); } } return $organized_pages; } function page_list($array) { $fakepages = array(); $fakepages[0] = array('id' => 1, 'parent_id' => 0, 'title' => 'Parent Page'); $fakepages[1] = array('id' => 2, 'parent_id' => 1, 'title' => 'Sub Page'); $fakepages[2] = array('id' => 3, 'parent_id' => 2, 'title' => 'Sub Sub Page'); $fakepages[3] = array('id' => 4, 'parent_id' => 3, 'title' => 'Another Parent Page'); $pages = $this->page_walk($fakepages, 0); print_r($pages); } 

Answer 1

A few very simple, common trees:

 function buildTree(array $elements, $parentId = 0) { $branch = array(); foreach ($elements as $element) { if ($element['parent_id'] == $parentId) { $children = buildTree($elements, $element['id']); if ($children) { $element['children'] = $children; } $branch[] = $element; } } return $branch; } $tree = buildTree($rows); 

The algorithm is pretty simple:

• Take an array of all elements and the identifier of the current parent (initially 0 / nothing / null / whatever).
• Scroll through all the items.
• If the parent_id element of the element matches the current parent identifier that you received in 1., this element is a child of the parent element. Put it on the list of current children (here: $branch ).
• Call the function recursively with the identifier of the element you just identified in 3., i.e. Find all the children of this element and add them as the children element.
• Return the list of children found.

In other words, one execution of this function returns a list of elements that are children of this parent identifier. Call it buildTree($myArray, 1) , it will return a list of elements that have a parent identifier 1. Initially, this function is called with a parent identifier equal to 0, so elements without a parent identifier, which are the root nodes, are returned. The function calls itself recursively to find children of children.

Answer 2

I know this question is old, but I ran into very similar problems - except for a very large amount of data. After some struggle, I managed to build a tree in one pass from a set of results - using links. This code is not very good, but it works, and it works pretty fast. It is not recursive - that is, only one pass through the result set, and then one array_filter at the end:

 $dbh = new PDO(CONNECT_STRING, USERNAME, PASSWORD); $dbs = $dbh->query("SELECT n_id, n_parent_id from test_table order by n_parent_id, n_id"); $elems = array(); while(($row = $dbs->fetch(PDO::FETCH_ASSOC)) !== FALSE) { $row['children'] = array(); $vn = "row" . $row['n_id']; ${$vn} = $row; if(!is_null($row['n_parent_id'])) { $vp = "parent" . $row['n_parent_id']; if(isset($data[$row['n_parent_id']])) { ${$vp} = $data[$row['n_parent_id']]; } else { ${$vp} = array('n_id' => $row['n_parent_id'], 'n_parent_id' => null, 'children' => array()); $data[$row['n_parent_id']] = &${$vp}; } ${$vp}['children'][] = &${$vn}; $data[$row['n_parent_id']] = ${$vp}; } $data[$row['n_id']] = &${$vn}; } $dbs->closeCursor(); $result = array_filter($data, function($elem) { return is_null($elem['n_parent_id']); }); print_r($result); 

When executed from this data:

 mysql> select * from test_table; +------+-------------+ | n_id | n_parent_id | +------+-------------+ | 1 | NULL | | 2 | NULL | | 3 | 1 | | 4 | 1 | | 5 | 2 | | 6 | 2 | | 7 | 5 | | 8 | 5 | +------+-------------+ 

The last print_r produces this output:

 Array ( [1] => Array ( [n_id] => 1 [n_parent_id] => [children] => Array ( [3] => Array ( [n_id] => 3 [n_parent_id] => 1 [children] => Array ( ) ) [4] => Array ( [n_id] => 4 [n_parent_id] => 1 [children] => Array ( ) ) ) ) [2] => Array ( [n_id] => 2 [n_parent_id] => [children] => Array ( [5] => Array ( [n_id] => 5 [n_parent_id] => 2 [children] => Array ( [7] => Array ( [n_id] => 7 [n_parent_id] => 5 [children] => Array ( ) ) [8] => Array ( [n_id] => 8 [n_parent_id] => 5 [children] => Array ( ) ) ) ) [6] => Array ( [n_id] => 6 [n_parent_id] => 2 [children] => Array ( ) ) ) ) ) 

This is exactly what I was looking for.

Answer 3

You can use php to get the mysql result into an array and then use it.

 $categoryArr = Array(); while($categoryRow = mysql_fetch_array($category_query_result)){ $categoryArr[] = array('parentid'=>$categoryRow['parent_id'], 'id'=>$categoryRow['id']); } 

Answer 4

For large arrays:

pass an array by reference.

 function buildTree(&$elements, $parentId = 0) { //pass main array by reference $branch = array(); foreach ($elements as $key => $element) { if ($element['parent_id'] == $parentId) { $element['children'] = buildTree($elements, $element['id']); $branch[] = $element; } } return $branch; } $tree = buildTree($rows); 

If you pass an array of be reference, then the same array will be used in every recursive function, there is no need to merge the parent child arrays at the end

Answer 5

Why is this buildTree function not working on my array.

Array ([5] => Array ([id] => 5 [parent_id] => 4 [data_level] => [data_prefix] => [data_title] => Assets [data_link] => 0)

[57] => Array ([id] => 57 [parent_id] => 5 [data_level] => [data_prefix] => [data_title] => Fixed assets [data_link] => 0)

[52] => Array ([id] => 52 [parent_id] => 5 [data_level] => [data_prefix] => [data_title] => Second asset [data_link] => 1)

[51] => Array ([id] => 51 [parent_id] => 5 [data_level] => [data_prefix] => [data_title] => Assset ONE [data_link] => 1)

[48] ​​=> Array ([id] => 48 [parent_id] => 4 [data_level] => [data_prefix] => [data_title] => Costs [data_link] => 0)

[50] => Array ([id] => 50 [parent_id] => 48 [data_level] => [data_prefix] => [data_title] => First flow [data_link] => 1)

[49] => Array ([id] => 49 [parent_id] => 48 [data_level] => [data_prefix] => [data_title] => First flow [data_link] => 1)

[58] => Array ([id] => 58 [parent_id] => 57 [data_level] => [data_prefix] => [data_title] => Vehicles [data_link] => 1)

)