Creating a multilevel array using parentIds in PHP

Question

I'm trying to setup a list that can have multiple levels, using parentId to define its parent. The first item's parentId is NULL. Example of some entries:

id parentId name
1    NULL     item1
2    NULL     item2
3    1        item3
4    2        item4
5    3        item5
6    3        item6

So, 1 and 2 are main items; 3 is a child of 1; 4 is a child of 2; 5 is a child of 3 (which is a child of 1 itself); 6 is also a child of 3 (which is a child of 1 itself); etc.

I'm stuck creating an array that correctly adds these items to the right levels. It should look like this:

Array
(
    [1] => Array
        (
            [name] => item1
            [parentId] => 
            [children] => Array
                (
                    [3] => Array
                        (
                            [name] => item3
                            [parentId] => 1
                            [children] => Array
                                (
                                    [5] => Array
                                        (
                                            [name] => item5
                                            [parentId] => 3
                                        )

                                    [6] => Array
                                        (
                                            [name] => item6
                                            [parentId] => 3
                                        )

                                )

                        )

                )

        )

    [2] => Array
        (
            [name] => item2
            [parentId] => 
            [children] => Array
                (
                    [4] => Array
                        (
                            [name] => item4
                            [parentId] => 2
                        )

                )

        )

)

But say I go through all the items using foreach(), and I get to item 5. Its parentId is 3, but at that point, I have no idea where this parent 3 is located in the array, and how to add children to that parent.

Is there a trick to loop through these items, and put them all in place the right way?

Answer 1

You should use the ID of an item as key value for the array, so that you can add an item to it's parent this way:

$array[$parentID]['children'][$childID] = array();

Answer 2

First thing that comes to mind is just a flat version of what you have there:

array (
[0] => array(
    'name' => 'item1',
    'parent' => null
    ),
[1] => array(
    'name' => 'item2',
    'parent' => null
    ),
[3] => array(
    'name' => 'item3',
    'parent' => 0
    ),
[4] => array(
    'name' => 'item4',
    'parent' => 3
    ),
[5] => array(
    'name' => 'item5',
    'parent' => 1
    ),
[6] => array(
    'name' => 'item6',
    'parent' => 1
    ), );

Basically, you only ever reference back to the parent. To find all the children, you'd have to loop through the array. The initial setup time would be pretty quick, though.

The second one that comes to mind, and would involve a lot more setup, but a lot less access time later on:

array (
[0] => array(
    'name' => 'item1',
    'parent' => null,
    'children' = array(3)
    ),
[1] => array(
    'name' => 'item2',
    'parent' => null
    'children' = array(5, 6)
    ),
[3] => array(
    'name' => 'item3',
    'parent' => 0
    'children' = array(4)
    ),
[4] => array(
    'name' => 'item4',
    'parent' => 3
    'children' = array()
    ),
[5] => array(
    'name' => 'item5',
    'parent' => 1
    'children' = array()
    ),
[6] => array(
    'name' => 'item6',
    'parent' => 1
    'children' = array()
    ), );

In this one, you'd be adding all the child indexes to the parent. It would take a little bit longer, but subsequent access times would be quick. As you're figuring out the parents, you simply append to the parent's children array.

The only real downside to the second approach is that if you want to add or remove an item, you have to remember to go back and update the children array for the parent.

Answer 3

Here goes

// your original data as an array
$data = array(
    array(
        'id' => 1,
        'parentId' => null,
        'name' => 'item1'
    ),
    array(
        'id' => 2,
        'parentId' => null,
        'name' => 'item2'
    ),
    array(
        'id' => 3,
        'parentId' => 1,
        'name' => 'item3'
    ),
    array(
        'id' => 4,
        'parentId' => 2,
        'name' => 'item4'
    ),
    array(
        'id' => 5,
        'parentId' => 3,
        'name' => 'item5'
    ),
    array(
        'id' => 6,
        'parentId' => 3,
        'name' => 'item6'
    ),
);

A recursive function

function buildTree( $ar, $pid = null ) {
    $op = array();
    foreach( $ar as $item ) {
        if( $item['parentId'] == $pid ) {
            $op[$item['id']] = array(
                'name' => $item['name'],
                'parentId' => $item['parentId']
            );
            // using recursion
            $children =  buildTree( $ar, $item['id'] );
            if( $children ) {
                $op[$item['id']]['children'] = $children;
            }
        }
    }
    return $op;
}

print_r( buildTree( $data ) );

/*
Array
(
    [1] => Array
        (
            [name] => item1
            [parentId] => 
            [children] => Array
                (
                    [3] => Array
                        (
                            [name] => item3
                            [parentId] => 1
                            [children] => Array
                                (
                                    [5] => Array
                                        (
                                            [name] => item5
                                            [parentId] => 3
                                        )

                                    [6] => Array
                                        (
                                            [name] => item6
                                            [parentId] => 3
                                        )

                                )

                        )

                )

        )

    [2] => Array
        (
            [name] => item2
            [parentId] => 
            [children] => Array
                (
                    [4] => Array
                        (
                            [name] => item4
                            [parentId] => 2
                        )

                )

        )

)
*/