When retrieving a group of objects from a database, sometimes we need to recreate some hierarchy inside a multidimensional array or object for further processing. However, since the language wasn’t developed with such usage scenarios in mind, the way to achieve this is anything but intuitive. Many developers just adjust their DB structure in order to make such sorting easier, but it’s always good to have a choice. I recently came across this problem myself, and think the solution I came up with is not only interesting, but could be useful to other developers out there. If you find this useful, or would like to propose a different solution, I’d love to read your comments below.

The Problem

Let’s say, as an example, that you have a DB table with columns id and parent, where id is an auto-generated primary key, and parent refers to id by a foreign key. The idea is every entry has either a parent in the same table, or a NULL parent and hence is at the top level of the hierarchy. We do not know how deep the hierarchy goes, and must be able to recursively populate a multidimensional array or object in order to recreate it.

The (Generic) Solution

First of all, we assume we are retrieving all entries into a plain array. We ORDER BY parent ASC, with NULLS first so we process the top level entries first. We will need to create 2 arrays, one for storing the entries hierarchically, and the other to keep track of the path of each entry inside the hierarchy. We will be dealing with arrays exclusively in this example, but using objects instead is pretty straightforward.

$entries = yourGetEntriesFromDbFunction();  //The array with our retrieved DB entries
$entryRecords = array();                    //Our hierarchy will be created in this array
//We will track the path of each entry here, with an array
//for each entry containing the ids of all its ancestors:
$entryPaths = array();
foreach ($entries as $entry) {
    //Create a new key inside each entry to store its children:
    $entry['children'] = array();
    $entryPaths[$entry['id']] = array();    //Make a space for the path of the entry
    if ($entry['parent'] === NULL) {        //If top level, just insert into the hierarchy array
        $entryRecords[$entry['id']] = $entry;
    } else {
    	$pathRef =& $entryRecords;          //Save a reference to the top level of our hierarchy
        //Traverse our current hierarchy based on the path of the entry's parent by reassigning a
        //single variable by reference to the children container of each level in the hierarchy:
        foreach ($entryPaths[$entry['parent']] as $path) {
    		$pathRef =& $pathRef[$path]['children'];
    	}
        //Once we reach the entry's parent's children container, just add the entry to it:
        $pathRef[] = $entry;
        //Register the entry's path by first copying parent's path
        $entryPaths[$entry['id']] = $entryPaths[$entry['parent']];
    }
    $entryPaths[$entry['id']][] = $entry['id']; //Finally add the id of the entry to its path
}

As you can see, the main idea is to save the path of each entry we insert in order to know how to get to it, and then traverse the path of the parent by reassigning references to the children container of each post in the path. This way we can always reach the parent of a post inside our hierarchy, no matter how complicated, provided that all parents are inserted before their children into it.

Speak Yii to me

Actually, I came up with this algorithm while working with Active Records on Yii Framework, so might as well share the code that inspired this post. I have a Section Model, with id, parent, and order columns. id and parent are as in the above example, but the order column provides the order in which the children in a post should be sorted. I added a public property named “children” to the Model in order to be able to store a record’s children in it, but that’s all. Since it’s the same principle as above, it’s mostly uncommented:

$sections = Section::model()->findAll(
    array('order'=>'parent ASC NULLS FIRST,"order"'));  //PostgreSQL FTW
$entryRecords = array();
$entryPaths = array();
foreach ($sections as $section) {
	$section->children = array();
    $entryPaths[$section->id] = array();
    if ($section->parent === NULL) {
        $entryRecords[$section->order] = $section;
    } else {
    	$pathRef =& $entryRecords;
        foreach ($entryPaths[$section->parent] as $path) {
    		$pathRef =& $pathRef[$path]->children;
    	}
        $pathRef[] = $section;
        $entryPaths[$section->id] = $entryPaths[$section->parent]; 
    }
    $entryPaths[$section->id][] = $section->order;
}

Hope you find some of this as useful as I did, and if you find this solution pretty obvious or even intuitive, congratulations: you’re a better web developer than I am.