stackoverflow/29405568/Recursive function to create tree

<?php // https://stackoverflow.com/questions/29396521/recursive-function-to-create-a-folder-tree-from-array

/*
 * source data notes:
 * 1) It not load in one pass.
 *
 * 2) The node 666 will fail to be added as there no parent for it - ever!
 *
 *  - this is important when testing
 *    As when adding nodes in a 'random order' we cannot be sure that all
 *    'source nodes' belong in the 'tree'! The code must allow for that.
 */

$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),
);

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

// var_dump($sourceKeys, $roots, array_keys($source));

// output tree built in here
$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 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);

// 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;


/**
 * Insert:  Find the 'parent' node
 *              if child not found within parent 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
 *                 This will always contain an entry called 'children'
 *                 that will be a list of 'child nodes' under this node.
 *
 * @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;
    }

    // is this the required parent?
    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
}