Algorithm for creating multi-dimensional array

Question

I'm using PHP and I need help with a seemingly simple task with an array.

This is my example array:

$arr = array(
    0  => NULL,
    1  => NULL,
    2  => NULL,
    3  => NULL,
    8  => '2',
    9  => '2',
    10 => '2',
    11 => '2',
    12 => '3',
    13 => '3',
    14 => '8',
    15 => '8',
    16 => '14',
    17 => '14',
    18 => '14'
);

The keys of the array represent the IDs (unique).
The values are the parentIDs, i.e. the ID of the parent "node". NULL means that there is no parentID (i.e. 1st dimension of the new array).

Now, I need to create a new, multi-dimensional array that has all the child elements under their parent IDs. (This probably sounds very confusing, sorry for my lack of descriptive abilities. There's an example below, which should make things clearer)

Here's what the new array of my example would look like after the "sorting" function, or whatever you call this, was applied:

$arr = array(
 0 => array(),
 1 => array(),
 2 => array(
     8 => array(
        14 => array(
            16 => array(),
            17 => array(),
            18 => array()
),
        15 => array()
),
     9 => array(),
    10 => array(),
    11 => array()
),
 3 => array(
    12 => array(),
    13 => array()
)
);

I know all the empty array()s are probably not a very clean and elegant solution but unfortunately this is the way I need it to be!

duplicate of http://stackoverflow.com/questions/4196157/create-array-tree-from-array-list — bcosca, Nov 21 '10 at 16:12
It's actually slightly different from my problem, my format is different. — user367217, Nov 21 '10 at 16:44

score 2 · Accepted Answer · answered Nov 21 '10 at 17:06

This recursive function will add the given datum to the correct parent, and should be called once for each element in your starting array.

function add_branch(&$tree, $datum, $parent) {

    // First we have the base cases:
    // If the parent is NULL then we don't need to look for the parent
    if ($parent == NULL) {
        $tree[$datum] = array();
        return true;
    }

    // If the array we've been given is empty, we return false, no parent found in this branch
    if (! count($tree)) {
        return false;
    }


    // We loop through each element at this level of the tree...
    foreach($tree as $key => $val) {

        // If we find the parent datum...
        if ($key == $parent) {

            // We add the new array in and we're done.
            $tree[$key][$datum] = array();
            return true;
        }

        // Otherwise, check all the child arrays
        else {

            // Now we check to see if the parent can be found in the curent branch
            // If a recursive call found a parent, we're done
            if (add_branch($tree[$key], $datum, $parent)) {
                return true;
            }
        }
    }

    // If none of the recursive calls found the parent, there's no match in this branch
    return false;

}

The comments are quite verbose, in the hope that you can understand what is going on. I'd encourage you to do a bit of reading on recursive functions to get your head around it.

This is how it would be used:

$arr = array(
 0 => NULL,
 1 => NULL,
 2 => NULL,
 3 => NULL,
 8 =>  '2',
 9 =>  '2',
10 =>  '2',
11 =>  '2',
12 =>  '3',
13 =>  '3',
14 =>  '8',
15 =>  '8',
16 => '14',
17 => '14',
18 => '14'
);


$final = array();

foreach ($arr as $datum => $parent) {
    add_branch($final, $datum, $parent);
}

$final now has the correct finishing array, as indicated in the question.

Kendall Hopkins · Answer 2 · 2010-11-21T17:04:53.593

Two pass foreach does the trick. This will link all child to their parents recursively.

//$array is the input

//The tree starts out as a flat array of the nodes
$tree = array_combine(
    array_keys( $array ),
    array_fill( 0, count( $array ), array() )
);

//link children to parents (by reference)
foreach( $tree as $key => &$row ) {
    if( ! is_null( $array[$key] ) ) {
        $tree[ $array[$key] ][ $key ] =& $row;
    }
}

//remove non-root nodes
foreach( array_keys( $tree ) as $key ) {
    if( ! is_null( $array[$key] ) ) {
        unset( $tree[ $key ] );
    }
}

Algorithm for creating multi-dimensional array

2 Answers2