Recursivly ordenate array with id and parent_id structure

Question

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?

Gumbo · Accepted Answer · 2011-11-30T14:43:30.800

5

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'].

edited Nov 30 '11 at 14:43

answered Nov 30 '11 at 11:47

Gumbo

643,351
109
780
844

Well... it works PERFECT! I never thought it would be "so simple"! I guess I "over think" it and went the hard (and supposedly wrong) way to do it. The only problem is that I don't fully understand the code :\ Can you, please, explain it a little bit? – MGP Nov 30 '11 at 12:00
@MARCOGPINTO What don’t you understand? – Gumbo Nov 30 '11 at 12:08
I kind of understand the logic, but let's imagine that I want to add a field where I save the path to that node, for example, for node 5 I save 2-4-5. I don't get exactly where I can do this in that foreach.. :\ – MGP Nov 30 '11 at 12:33
After a few minutes, with some echos to see what happen exactly on the foreach, i got all the logic and how to work with it! Thanks a lot for your help! :) – MGP Nov 30 '11 at 14:02
@MARCOGPINTO: Composing the absolute path can be done in a similar manner: Since each new node is inserted as a child node of an already existing node inside the tree, compose the path to that new node by using the path of the parent node and extend it by the new node’s ID. E. g.: `$path = $parent['path'] + array($val['id']);` while the root’s path is an empty array (`$tree = array('children' => array(), 'path' => array())`). – Gumbo Nov 30 '11 at 14:39
That's what I thought. Once again, thanks a lot for your help! :) – MGP Nov 30 '11 at 16:16

Recursivly ordenate array with id and parent_id structure

1 Answers1

Linked