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 may not need a new solution anymore, but this might come in handy for other users:

// ! assuming $elements is built like: Array( id1 => Array(/*parameters*/) , ...)

function buildTree($elements) {

    $e = Array(0 => Array()); // elements array
    $r = Array(0 =>& Array()); // reference array

    while ($elements) {// repeat till $elements is empty

        // loop through (remaining) elements
        foreach ($elements as $id => $element) {

            $pid = $element['parentId']; // shortcut

            if (array_key_exists($pid,$r)) { // parent already parsed -> can add this element

                // use parent's reference to elements array to add this element ( $r[$pid] =& $e[path][to][$pid] )
                $r[$pid] ['elements'][$id] = $element;

                // create reference for this element using parent's reference
                $r[$id] =& $r[$pid]['elements'][$id];

                // unset current element in input array in order to limit while-loop
                unset($elements[$id]);

            }

        }
    }

return $e; // or whatever you need, the reference array can be useful if you need to fetch an element only knowing its id

}

What it does:

• declare an array for the results ($e) and add a root element (0/null)
• declare an array for the references ($r) and already reference $r[0] to $e[0]
• loop through the input array till it's empty
  • do for each element:
  • check if parent already is handled, if so, you know where this element belongs and can add it
    (this is what prevented me from getting it working the first couple attempts and why the while loop is needed)
  • add the current element using parent's reference (note the & after = !)
  • create a new reference using the parent's reference
  • unset the current element from the input array
    (you can leave this if you like infinite while loops ;) )
• of cource return what you need!

The benefits of this method are:

• you reduce the amount of foreach loops (you assign the most you can from what you know at the moment)
• each loop gets shorter because you unset parsed elements in the input array ($elements)
• you can also return the reference array and be able to quickly get the element's parameters assuming you know it's id

In other words: it should be faster (I haven't tested it!), at least for more complex tasks like the one I use it for.

Answer 2

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
                        )

                )

        )

)
*/

Answer 3

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 4

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