A recursive function to sort through parent and child nodes in PHP using a foreach loop on an array

Question

I have a data set stored in an array that references itself with parent-child ids: id, parent_id, title etc. The top tier has a parent_id of 0, and there can be countless parent-child relationships.

So I'm sorting through this array with a foreach loop within a recursive function to check each array element against its parent element, and I think I've been staring at this method too long.

I do end up with the elements in the correct order, but I can't seem to get my lists nested correctly, which makes me think that the method doesn't really work.

Is this the best route to take?
What can I do to improve and fix this method
Is there another trick that I can apply?

Here is my source:

<div>
    <div>Subpages</div>

    <ul>
    <?php subPages($this->subpages->toArray(), 0) ?>
    </ul>
    <br>
    <a href="javascript:;" onclick="">Add New Subpage</a>
</div>

<?php
    function subPages($subpages, $parent){

        foreach($subpages as $key => &$page){

            $newParent =  $page['id'];

            //If the current page is the parrent start a new list
            if($page['id'] == $parent)
            {
                //Echo out a new list
                echo '<ul>';
                echo '<li class="collapsed">';
                echo '<a href="javascript:;" class="toggle">+</a>';
                echo '<a href="javascript:;" onclick="">'.$page['title'].'</a>';        

                subPages($subpages, $newParent);

                echo '</li>';
                echo '</ul>';
            }
            //If the page's parent id matches the parent provided
            else if($page['parent_id'] == $parent)
            {
                //Echo out the link
                echo '<li class="collapsed">';
                echo '<a href="javascript:;" class="toggle">+</a>';
                echo '<a href="javascript:;" onclick="">'.$page['title'].'</a>';

                //Set the page as the new parent
                $newParent = $page['id'];

                //Remove page from array
                unset($subpages[$key]);

                //Check the rest of the array for children
                subPages($subpages, $newParent);

                echo '</li>';
            }
        }
    }
?>

As always, any assistance is appreciated. Please let me know if something isn't clear.

It sounds like you're describing a [`depth-first search`](http://en.wikipedia.org/wiki/Depth-first_search) of a tree. Or maybe [`heapsort`](http://en.wikipedia.org/wiki/Heapsort). — Matt, Aug 16 '12 at 15:28
either restructure your tree or process the iteration using a queue and only add to the queue if no already in there or in the processed list. — Waygood, Aug 16 '12 at 15:31
So there's no elegant way to traverse and spit out the data? — dbergunder, Aug 16 '12 at 20:54

score 2 · Accepted Answer · answered May 25 '13 at 19:24

I doubt that you guys are still looking for a real answer to this, but it might help out others with the same problem. Below is a recursive function to resort an array placing children beneath parents.

$initial = array(
    array(
        'name' => 'People',
        'ID' => 2,
        'parent' => 0
        ),
    array(
        'name' => 'Paul',
        'ID' => 4,
        'parent' => 2
        ),
    array(
        'name' => 'Liz',
        'ID' => 5,
        'parent' => 2
        ),
    array(
        'name' => 'Comus',
        'ID' => 6,
        'parent' => 3
        ),
    array(
        'name' => 'Mai',
        'ID' => 7,
        'parent' => 2
        ),
    array(
        'name' => 'Titus',
        'ID' => 8,
        'parent' => 3
        ),
    array(
        'name' => 'Adult',
        'ID' => 9,
        'parent' => 6
        ),
    array(
        'name' => 'Puppy',
        'ID' => 10,
        'parent' => 8
        ),
    array(
        'name' => 'Programmers',
        'ID' => 11,
        'parent' => 4
        )   ,
    array(
        'name' => 'Animals',
        'ID' => 3,
        'parent' => 0
        )                           
    );


/*---------------------------------
function parentChildSort_r
$idField        = The item's ID identifier (required)
$parentField    = The item's parent identifier (required)
$els            = The array (required)
$parentID       = The parent ID for which to sort (internal)
$result     = The result set (internal)
$depth          = The depth (internal)
----------------------------------*/

function parentChildSort_r($idField, $parentField, $els, $parentID = 0, &$result = array(), &$depth = 0){
    foreach ($els as $key => $value):
        if ($value[$parentField] == $parentID){
            $value['depth'] = $depth;
            array_push($result, $value);
            unset($els[$key]);
            $oldParent = $parentID; 
            $parentID = $value[$idField];
            $depth++;
            parentChildSort_r($idField,$parentField, $els, $parentID, $result, $depth);
            $parentID = $oldParent;
            $depth--;
        }
    endforeach;
    return $result;
}

$result = parentChildSort_r('ID','parent',$initial);

print '<pre>';
print_r($result);
print '</pre>';

It's a wind down method that removes elements from the original array and places them into result set in the proper order. I made it somewhat generic for you, so it just needs you to tell it what your 'ID' field and 'parent' fields are called. Top level items are required to have a parent_id (however you name it) of 0. I also add a depth marker to each item so that you can format on output.

Paul T. Rawkeen · Answer 2 · 2012-08-16T15:50:09.567

I will try to help you.

It is possible to compose such relations in one pass:

    /**
     * Used for "recursive" folding of layout items
     * Algorithm of infinite tree (non recursive method)
     * 
     * @param array $items
     * @return array
     */
    function _foldItems($items) {

        $result = array();

        foreach ($items as $key => $item) {

            $itemName = $item['name'];

            if (!isset($item['parent']))
                continue;
            else {

                $parentName = $item['parent']; // it can be either `name` or some `id` of the parent item

                if (isset($result[$itemName][$item['sequence']])) {

                    // Done to eliminate `Warning: Cannot use a scalar value as an array in atLeisure_PropertyImport.class.php`
                    // Sometimes elements already in the list and have [name] => $count and next line tries to put item in array (item becomes parent)
                    if (    isset($result[$parentName][$item['parentSequence']]['items'][$itemName]) AND
                            is_scalar($result[$parentName][$item['parentSequence']]['items'][$itemName])
                        )
                        $result[$parentName][$item['parentSequence']]['items'][$itemName] = array();

                    $result[$parentName][$item['parentSequence']]['items'][$itemName][$item['sequence']] = $result[$itemName][$item['sequence']];

                    unset($result[$itemName][$item['sequence']]);
                } else
                    $result[$parentName][$item['parentSequence']]['items'][$itemName] = $item['count'];

                unset($items[$key]);

                } // if //

            if (empty($result[$itemName]))
                unset($result[$itemName]);

        } // foreach //

        foreach ($items as $item) { // enumerating rest of the items (single items)
            $itemName = $item['itemName'];

            if (!isset($result[$itemName]))
                $result[$itemName][$item['sequence']] = $item['count'];
        }

        return $result;

    }

Example can be a bit hard to read and to understand because there is really too much code, but I've made this function not so long ago for one project and it seems to be work successfully.

NOTE: It will also work if there are several same items linked to one parent item. It uses item sequence number to avoid aliasing similar values into one.

A recursive function to sort through parent and child nodes in PHP using a foreach loop on an array

2 Answers2

Linked