Categories and sub categories. Directories and sub directories. Building a tree of nodes that have parents is a common problem these days.
There are two solutions to this problem, but unfortunately, the inefficient one is often used by programmers, due to the lack of time, or to inexperience.
Imagine, for the sake of clarity, a simple dataset that goes as follow:
Array
(
[0] => Array
(
[name] => Node 0
[parent] => null
)
[1] => Array
(
[name] => Node 1
[parent] => 4
)
[2] => Array
(
[name] => Node 2
[parent] => 8
)
...
The common approach is to use a recursive function that finds all the root nodes, then all their sub nodes, then all the sub nodes of their sub nodes, and so on.
function mapTree($dataset, $parent=null) {
$tree = array();
foreach ($dataset as $id=>$node) {
if ($node['parent'] !== $parent) continue;
$node['children'] = mapTree($dataset, $id);
$tree[$id] = $node;
}
return $tree;
}
The problem with this method is that, in terms of calculation, the problem complexity is exponential: you need to search all the dataset for children nodes for each node. Thus, building a tree of 1,000 nodes is 100 times more complicated than building a tree of 100 nodes, because you will have to search 10 times more nodes, 10 times more often.
A more efficient way to build the tree is to use dereferencing. This allows to map the whole tree in a single pass, without recursion. The problem complexity then becomes linear rather than exponential, and 10 times more nodes equals to 10 times more time (although the time required by PHP to find a specific index of an array isn’t taken into account here).
function mapTree($dataset) {
$tree = array();
foreach ($dataset as $id=>&$node) {
if ($node['parent'] === null) { // root node
$tree[$id] = &$node;
} else { // sub node
if (!isset($dataset[$node['parent']]['children'])) $dataset[$node['parent']]['childs'] = array();
$dataset[$node['parent']]['children'][$id] = &$node;
}
}
return $tree;
}
The full PHP code of examples can be found below:
tree.zip (1.2k)
Tree image from Wikipedia.org
If you like this article, leaving a comment, tweeting ofr liking it is always appreciated.
Thursday 6 November 2008 5:15 am
Thank you so much for publishing this article. I’m an experienced programmer but I was so struggling with this.
Harry
Tuesday 17 March 2009 8:01 am
Wow, this was perfect, I was having to resolve this myself by resorting to recursive techniques when I stumbled upon this whilst trying to figure out how to code without the recursion. Many thanks!
Google search terms used: ‘php build array parent children’
Wednesday 21 October 2009 4:44 pm
Doesn’t seem to act properly under PHP 5.1.6., whereas under 5.2.6 it functions as expected just that the older version only returns the parents in some cases, and the first parent and a couple children … depending on what order the inputted list is.
Saturday 8 May 2010 5:26 pm
Nice example but how would you show the number of parents a sibling has without going exponential?
Friday 14 May 2010 8:21 am
This is a great solution and amazingly fast. But it seems that it doesn’t work with PHP 5.2.0, while it works fine with 5.2.5. I found that on 5.2.5, there is an additional loop creating the root node, while on 5.2.0 this last iteration is omitted. Is there any solution for this issue?
Tuesday 8 June 2010 3:38 am
Hmmm…
I get: Notice: Undefined index: parent in path/file.php on line 95
When trying to mapTree($dataset);
My dataset looks like this:
array( 0 => array( ‘parent’ => 0, ‘name’ => ‘Node 0′ ), 1 => array( ‘parent’ => 0, ‘name’ => ‘Node 1′ ) ); … etc
Author, any ideas on how to fix this? Your script is works only for the data structure that you build from loop… if you take the same from DB it wont work.
The category itself – is the main array key? array( 0 => array( ‘parent’.. — this 0 is category id 0 ?
Tuesday 22 June 2010 1:26 pm
Hi, Thanks for this article.
I want to use this with a database, could you pleae tell me what fields I have to have in the table?
Monday 28 June 2010 8:31 am
$levellimit is not correct….in my previous post remove them when i can fix that then i will post here