Tree, in computingCategories 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:

PHP Source tree.zip (1.2k)

Tree image from Wikipedia.org


If you like this article, leaving a comment, tweeting ofr liking it is always appreciated.

category PHP, Programming Wednesday 10 September 2008 Comments (8)

8 Responses :

  1. Harry

    Thank you so much for publishing this article. I’m an experienced programmer but I was so struggling with this.

    Harry

  2. Jez

    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’

  3. Brantone

    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.

  4. Freeman Jackson

    Nice example but how would you show the number of parents a sibling has without going exponential?

  5. Webbird

    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?

  6. Fratyr

    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 ?

  7. Sean

    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?

  8. HADI

    $levellimit is not correct….in my previous post remove them when i can fix that then i will post here

Leave a Reply