VGTech is a blog where the developers and devops of Norways most visited website share code and tricks of the trade… Read more

Building Tree Structures in PHP Using References

by André Roaldseth in PHP
PHP

Using a recursive function or joining in SQL usually are the most common ways for creating tree structures. Both these solutions are of exponential time complexity 2O(n) and therefore very expensive in computational time. For every element you add to the dataset the computational time theoretically doubles.

While researching in best practices for building tree structures I found this method using references. Using references, the tree is built with only one pass. This gives a time complexity of O(n), which is completely linear. For every element you add to the dataset you get only a small and constant increase in computational time.

The following code is a modified version of Tommy Lacroix’ solution as I found it to be a bit troublesome when using datasets from Zend_Db. Now you can do a $dataset->toArray() and the $references array will make sure it comes out correctly.

Show code
function buildTree(array $dataset) {
    $tree = array();

	/* Most datasets in the wild are enumerative arrays and we need associative array
	   where the same ID used for addressing parents is used. We make associative
	   array on the fly */
    $references = array();
    foreach ($dataset as $id => &$node) {
    	// Add the node to our associative array using it's ID as key
        $references[$node['id']] = &$node;

        // Add empty placeholder for children
        $node['children'] = array();

		// It it's a root node, we add it directly to the tree
        if (is_null($node['parentId'])) {
            $tree[$node['id']] = &$node;
        } else {
        	// It was not a root node, add this node as a reference in the parent.
            $references[$node['parentId']]['children'][$node['id']] = &$node;
        }
    }

    return $tree;
}

Developer at VG. @androa

Recent posts in PHP

2 comments

  • Tor

    This is called modified preorder tree traversal or nested sets.

  • Tung, Nguyen Dam

    function create($data){
    foreach($data as &$v){
    // Get childs
    if(isset(self::$tree[$v['id']])) $v['child'] =& self::$tree[$v['id']];

    // push node into parent
    self::$tree[$v['pid']][$v['id']] =& $v;

    // push child into node
    self::$tree[$v['id']] =& $v['child'];
    }

    // return Tree
    return self::$tree[0];
    }

Leave your comment