CODEWITHSUNDEEP
phparraysrecursion
MGP
MGP

Reputation: 653

Recursivly ordenate array with id and parent_id structure

So, I got this array (data gather from a database):

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 0
        )

    [1] => Array
        (
            [id] => 2
            [parent_id] => 0
        )

    [2] => Array
        (
            [id] => 3
            [parent_id] => 2
        )

    [3] => Array
        (
            [id] => 4
            [parent_id] => 2
        )

    [4] => Array
        (
            [id] => 5
            [parent_id] => 4
        )
)

and I'm trying to create and ordered array like this:

Array
(
    [1] => Array
        (
            [parent_id] => 0
        )

    [2] => Array
        (
            [parent_id] => 0
            [children] => Array
            (
                [3] => Array
                    (
                        [parent_id] => 2
                    )

                [4] => Array
                    (
                        [parent_id] => 2
                        [children] => Array
                        (
                            [5] => Array
                                (
                                    [parent_id] => 4
                                )
                        )
                    )
            )
        )
)

and I tried with the following code:

function placeInParent(&$newList, $item)
{
    if (isset($newList[$item['parent_id']]))
    {
        $newList[$item['parent_id']]['children'][$item['id']] = $item;
        return true;
    }

    foreach ($newList as $newItem)
    {
        if (isset($newItem['children']))
        {
            if (placeInParent($newItem['children'], $item))
            {
                return true;
            }
        }
    }
    return false;
}

$oldList = (first array above)

$newList = array();

foreach ($oldList as $item)
{
    if ($item['parent_id'] == 0)
    {
        $newList[$item['id']] = $item;
    }
    else
    {
        placeInParent($newList, $item);
    }
}

but the problem is that I only get the first 2 levels of the array! The last one is lost.. and my ordered array turns out like this:

Array
(
    [1] => Array
        (
            [parent_id] => 0
        )

    [2] => Array
        (
            [parent_id] => 0
            [children] => Array
                (
                    [3] => Array
                        (
                            [parent_id] => 2
                        )

                    [4] => Array
                        (
                            [parent_id] => 2
                        )
                )
        )
)

I just can't get where I'm messing up :\ help?

Upvotes: 2

Views: 1582

Answers (1)

Gumbo
Gumbo

Reputation: 655825

You can do this without recursion with the help of an index that references the nodes inside the tree:

$arr = array(
    array('id'=>1, 'parent_id'=>0),
    array('id'=>2, 'parent_id'=>0),
    array('id'=>3, 'parent_id'=>2),
    array('id'=>4, 'parent_id'=>2),
    array('id'=>5, 'parent_id'=>4),
);

// array to build the final hierarchy
$tree = array(
    'children' => array(),
    'path'     => array()
);

// index array that references the inserted nodes
$index = array(0=>&$tree);

foreach ($arr as $key => $val) {
    // pick the parent node inside the tree by using the index
    $parent = &$index[$val['parent_id']];
    // append node to be inserted to the children array
    $node = array(
        'parent_id' => $val['parent_id'],
        'path'      => $parent['path'] + array($val['id'])
    );
    $parent['children'][$val['id']] = $node;
    // insert/update reference to recently inserted node inside the tree
    $index[$val['id']] = &$parent['children'][$val['id']];
}

The final array you are looking for is in $tree['children'].

Upvotes: 5

Related Questions