By David Hemphill


2011-12-21 09:09:25 8 Comments

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

For example: I'm fetching all the pages in one query, and this is the what the database table looks like

+-------+---------------+---------------------------+
|   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 I would like to end up with 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've looked and tried nearly every solution I've come across (there's a lot of them here on Stack Overflow, but have had no luck getting something generic enough that will work for both pages and categories.

Here's the closest I've gotten, but it doesn't work because I'm assigning the children to the first level parent.

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

3 comments

@Aleks G 2014-03-27 12:32:40

I know this question is old, but I Was facing a very similar problem - except with a very large amount of data. After some struggle, I managed to build the tree in one pass of the resultset - using references. This code is not pretty, but it works and it works quite fast. It's non-recursive - that is, there's only one pass over the resultset 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 on 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
                                (
                                )

                        )

                )

        )

)

Which is exactly what I was looking for.

@Swadesh 2014-06-21 15:40:24

You are amazing. This works perfectly for me. I was searching for this since last 2 days. This answer should be marked as best answer.

@Mohammadhzp 2015-08-14 02:47:57

while solution is smart, but this code has bug, it gave me different results on different situations

@Aleks G 2015-08-14 13:42:34

@Mohammadhzp I have been using this solution in production for the last year and had no problem with it. If your data is different, you'll get different results :)

@Mohammadhzp 2015-08-14 14:22:29

@AleksG : I upvote your answer before comment, I had to add isset($elem['children']) to the array_filter callback, something like this return isset($elem['children']) && is_null($elem['n_parent_id']); to get it working right

@Aleks G 2015-08-14 14:24:29

@Mohammadhzp With your change, the code will not work if a top-level element doesn't have any children - it will be removed from the array completely.

@Mohammadhzp 2015-08-14 14:43:53

@AleksG ,with using latest version of php that's not what happen to result for me, if I remove isset($elem['children']) and top-level element contain children, I would get two different array of that top-level element(one with children and one without)"I just tested again 2 minutes ago and without isset() I get different(wrong) result"

@michalzuber 2016-10-31 14:20:03

Thanks, but I had to change $elems = array(); to $data = array();

@deceze 2011-12-21 09:17:41

Some very simple, generic tree building:

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:

  1. Take the array of all elements and the id of the current parent (initially 0/nothing/null/whatever).
  2. Loop through all elements.
  3. If the parent_id of an element matches the current parent id you got in 1., the element is a child of the parent. Put it in your list of current children (here: $branch).
  4. Call the function recursively with the id of the element you have just identified in 3., i.e. find all children of that element, and add them as children element.
  5. Return your list of found children.

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

@deceze 2011-12-21 09:36:14

Glad it helps. To note: this is somewhat inefficient since it always passes the whole $elements array down. For small arrays that hardly matters, but for large data sets you'll want to remove the already matched element from it before passing it down. That becomes somewhat messy though, so I left it simple for your easier understanding. :)

@Jens Törnell 2013-01-24 13:37:12

@deceze I would like to see the messy version as well. Thanks in advance!

@Brownrice 2013-11-27 22:53:41

Please can someone explain what the first argument 'array' is in buildTree()? Should that be the var that you give to the initial array of pages etc. e.g '$tree = array'? Can someone also explain the last line '$tree = buildTree($rows)', as '$rows' is not defined anywhere? Lastly I am struggling with the HTML markup to generate the nested list.

@deceze 2013-11-28 07:12:34

@user array is a type hint for $elements, the first argument is simply array $elements. $rows is an array of database results like the one from the question.

@Brownrice 2013-11-29 11:35:10

@deceze Thank you, After reading [ php.net/manual/en/language.oop5.typehinting.php ] I see type hint is a function which was introduced in PHP version 5.

@Brownrice 2013-11-29 12:59:47

@deceze Please can you or someone who knows, comment the 'buildTree' function to explain each step?

@deceze 2013-11-29 13:15:29

@user I have added an explanation. Ignore the $children = buildTree(...) part and the function should be pretty obvious and simple.

@Sizzling Code 2014-12-03 07:00:19

Love your Work. Awesome Work.. Thankyou. Really needed something simple like this.

@DrDog 2015-04-20 22:41:03

its 2015 but this code came in handy! Upvote for you mate

@Marais Rossouw 2015-08-18 12:28:33

Is there anyway to track the parent id's here, and inject them as another array prop along the way? Kinda saving the path of each node?

@deceze 2015-08-18 12:33:58

@Marais Sure: make $parentId an array, append to the array and pass it through. buildTree(.., array_merge($parentId, array($element['id'])))

@Marais Rossouw 2015-08-18 12:37:11

@deceze - Not sure that'll work. laravel.io/bin/qQao6 EDIT: Added Link

@deceze 2015-08-18 12:46:16

@Marais It'd help if you assigned the result of array_merge to anything.

@Ulugov 2015-12-08 03:29:10

Thank you very much! Awesome solution!

@zoom 2017-06-20 16:19:46

I just tried this solution against my parent-child data over 10,000 rows, but the performance very slow. Is there any optimization tips for this?

@mustafa 2011-12-21 09:21:11

It is possible to use php to get the mysql result into array and then use it.

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

Related Questions

Sponsored Content

38 Answered Questions

[SOLVED] Deleting an element from an array in PHP

  • 2008-12-15 20:28:55
  • Ben
  • 2285788 View
  • 2253 Score
  • 38 Answer
  • Tags:   php arrays

79 Answered Questions

[SOLVED] How do I remove a particular element from an array in JavaScript?

  • 2011-04-23 22:17:18
  • Walker
  • 5767126 View
  • 7196 Score
  • 79 Answer
  • Tags:   javascript arrays

32 Answered Questions

[SOLVED] Create ArrayList from array

12 Answered Questions

[SOLVED] Build a tree from a flat array in PHP

  • 2012-01-12 18:28:19
  • DSkinner
  • 47321 View
  • 33 Score
  • 12 Answer
  • Tags:   php arrays tree flat

54 Answered Questions

[SOLVED] Remove duplicate values from JS array

29 Answered Questions

[SOLVED] How to create a generic array in Java?

2 Answered Questions

1 Answered Questions

[SOLVED] Recursive function to generate flat array from hierarchical array

3 Answered Questions

3 Answered Questions

Sponsored Content