Storing hierarchical data in a tabular data structure such as a database is not uncommon in many applications (eg. threaded comments on a blog entry, or a navigation menu structure). The “Adjacency List” method; probably the most common, involves storing a reference to the parent in each of the children.

Here is a snippet for converting the rows stored using the adjacency list method into a hierarchical array in PHP. My goal was to do this in 1 pass, without recursion. I ended up using 2 passes, I think 1 pass is achievable if you can guarantee the parent will always be returned before all of its children. But since I couldn’t, the first pass is to change the id of the row to be the key of the array.

function convertToTree(array $flat, $idField = 'id',
                        $parentIdField = 'parentId',
                        $childNodesField = 'childNodes') {
    $indexed = array();
    // first pass - get the array indexed by the primary id
    foreach ($flat as $row) {
        $indexed[$row[$idField]] = $row;
        $indexed[$row[$idField]][$childNodesField] = array();
    }  

    //second pass
    $root = null;
    foreach ($indexed as $id => $row) {
        $indexed[$row[$parentIdField]][$childNodesField][$id] =& $indexed[$id];
        if (!$row[$parentIdField]) {
            $root = $id;
        }
    }

    return array($root => $indexed[$root]);
}  

// Usage:
$rows = array(
    array(
        'id' => 1,
        'parentId' => null,
        'name' => 'Menu',
    ),
    array(
        'id' => 2,
        'parentId' => 1,
        'name' => 'Item 1-1',
    ),
    array(
        'id' => 3,
        'parentId' => 1,
        'name' => 'Item 2-1',
    ),
    array(
        'id' => 4,
        'parentId' => 1,
        'name' => 'Item 1-2',
    ),
);

convertToTree($rows);

// Produces:
array (
    1 => array(
        'id' => 1,
        'parentId' => NULL,
        'name' => 'Menu',
        'childNodes' => array(
            2 => array(
                'id' => 2,
                'parentId' => 1,
                'name' => 'Item 1-1',
                'childNodes' => array (
                    4 => array (
                        'id' => 4,
                        'parentId' => 2,
                        'name' => 'Item 1-2',
                        'childNodes' => array (
                        ),
                    ),
                ),
            ),
            3 =>  array (
                'id' => 3,
                'parentId' => 1,
                'name' => 'Item 2-1',
                'childNodes' => array (
                ),
            ),
        ),
    ),
)