Recursive function to create a folder tree from array

Question

So I have the following:

id           => the id of the folder
name         => the name of the folder
folder_id    => null if it's in the root, but will have the "id" of it's parent if it's inside another folder

I have all of these listed out in an array like so: (this will be $folder_array in my example)

Array (
    [1] => Array (
        [name] => folder1
        [id] => 1
        [folder_id] => null
    )
    [2] => Array (
        [name] => folder2
        [id] => 2
        [folder_id] => null
    )
    [3] => Array (
        [name] => folder3
        [id] => 3
        [folder_id] => 2
    )
    [4] => Array (
        [name] => folder4
        [id] => 4
        [folder_id] => 3
    )
}

I am trying to make an array that has a folder tree of sorts, so I'd like it to look like:

Array (
    [1] => Array (
        [name] => folder1
        [id] => 1
        [folder_id] => null
    )
    [2] => Array (
        [name] => folder2
        [id] => 2
        [folder_id] => null,
        [children] => Array (
            [3] => Array (
                [name] => folder3
                [id] => 3
                [folder_id] => 2,
                [children] => Array (
                    [4] => Array (
                        [name] => folder4
                        [id] => 4
                        [folder_id] => 3
                    )
                )
            )
        )
    )
}

So far I can get the first level of folders into it's right children array, but I'm having trouble getting multiple levels to go in.

Could anyone help me fix up this code so that I can make an effective folder tree. Also, if anyone has any more effective ways of organizing, I'd be open to that as well.

This is my code so far:

$folder_array = array(
    "1" => array("name"=> "folder1","id" => "1","folder_id" => null),
    "2" => array("name"=> "folder2","id" => "2","folder_id" => null),
    "3" => array("name"=> "folder3","id" => "3","folder_id" => "2"),
    "4" => array("name"=> "folder4","id" => "4","folder_id" => "3")
);

//a new array to store the folder tree in
$new_array = array();

//now search through each one that has no folder_id
foreach($folder_array as $folder)
{
    //if the folder id is empty, it means it is in the root(home) folder
    if(empty($folder['folder_id']))
    {
        $new_array[$folder['id']] = $folder_form_array[$folder['id']];

        //now go through folder_array again and see if it has any folders inside that one
        foreach($folder_array as $folder2)
        {
            //..and so on
        }
    }
}

Answer 1

This is a 'multi-way' tree with 'data' stored at the nodes.

Unless the source array is in order, such that 'parent' nodes come before 'child' nodes, then the tree will not build correctly if only one pass is used.

This version of the code will do multiple passes when trying to insert children.

To reduce the amount of array scanning, a separate list of nodes ($sourceKeys) is kept, and any inserted nodes are deleted from the list.

As usual: Working code at Eval.in - and - Full source code at Pastebin.com

Todo: test how expensive this is for large trees (maybe for an update?)

The function which tries to insert one node...

/**
 * Insert:  Find the 'parent' node
 *          if child not found then insert a 'node'
 *
 * @param array node passed by reference as the new node will be inserted
 * @param integer $parentId - root Id - may be null it indicate a 'root'
 * @param integer $childId
 * @param array   $folderInfo - the 'node data' to be stored

 * @return boolean  true if parentId found and child alive
 *                   false if parent not found anywhere in the tree
 */
function insertNode(&$node, $parentId, $childId, $folderInfo) {

    // is Root Node
    if (is_null($parentId)) {
        $node[$childId] = $folderInfo;
        $node[$childId]['children'] = array();
        return true;
    }

    if (isset($node[$parentId])) { // this node will be processed
        if (!isset($node[$parentId]['children'][$childId])) {
            $node[$parentId]['children'][$childId] = array_merge($folderInfo,
                                           array('children' => array())); // add child node
            return true;
        }
        return true; // end of processing
    }

    // check all the children of this node...
    foreach($node as $idx => &$child) { // need the reference
        if (count($child['children']) >= 1) { // check the children...
            if (insertNode($child['children'], $parentId, $childId, $folderInfo)) {
                return true;
            }
        }
    }
    return false; // parentId not in the tree
}

Start to process the data...

// extract the root nodes as we need those first...
$roots = array_filter($source, function($data) {
                                  return is_null($data['folder_id']);
                               });

// we need a list of child nodes that haven't been added yet
$sourceKeys = array_diff(array_keys($source), array_keys($roots));

Initialize output tree and process the root nodes...

$theTree = array();

// first we need to insert the roots... worth doing as a separate pass...
foreach($roots as  $idx => $folderInfo) {
    insertNode($theTree, $folderInfo['folder_id'], $folderInfo['id'], $folderInfo);
}

Now process the list of 'child nodes' that need to be added...

// now we do multiple passes down the source trying to insert nodes.
// We know we have finished when nothing is inserted during the pass.

// for efficiency, we will drive off the sourceKeys array after removing
// any inserted entries...

do {
    $insertCount = 0;

    foreach($sourceKeys as $position => $idx) {

        $folderInfo = $source[$idx];
        $inserted = insertNode($theTree, $folderInfo['folder_id'], $folderInfo['id'], $folderInfo);
        if ($inserted) {
            $insertCount++;
            unset($sourceKeys[$position]); // it is safe to do this in 'foreach'
        }
    }

} while ($insertCount > 0);

We are done... just some reporting to do...

// report nodes not inserted... this may be useful
foreach($sourceKeys as $idx) {
        var_dump('not inserted:', $source[$idx]);
}

// output the tree
echo '<pre>', 'Children are in the same order as the input array.', '<br />';
    print_r($theTree);
echo '</pre>';
exit;

Test Data - note: random order and one invalid node (666).

$source = Array (
   4 =>   Array("name" => "folder4",   "id" => 4,   "folder_id" => 3),
   11 =>  Array("name" => "folder11",  "id" => 11,  "folder_id" => 3),
   13 =>  Array("name" => "folder13",  "id" => 13,  "folder_id" => 12),
   31 =>  Array("name" => "folder31",  "id" => 31,  "folder_id" => 99),
   12 =>  Array("name" => "folder12",  "id" => 12,  "folder_id" => 98),
   42 =>  Array("name" => "folder42",  "id" => 42,  "folder_id" => 32),
   32 =>  Array("name" => "folder32",  "id" => 32,  "folder_id" => 99),
   666 => Array("name" => "folder666", "id" => 666, "folder_id" => 9999),
   99 =>   Array("name" => "folder99Root",   "id" => 99,   "folder_id" => null),
   3 =>   Array("name" => "folder3",   "id" => 3,   "folder_id" => 98),
   33 =>  Array("name" => "folder33",  "id" => 33,  "folder_id" => 99),
   98 =>   Array("name" => "folder98Root",   "id" => 98,   "folder_id" => null),
);