# Building Tree Structures in PHP Using References

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 2^{O(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.

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; }

## 7 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];

}

## kriplozoik

little mistake in one of the comments:

//If it's a root node...

nice work though

## kw5

function buildTree(array $dataset) {

$tree = array();

foreach ($dataset as $node) {

$id = $node['id'];

// add empty array of children

if (!isset($tree[$id]['children'])) {

$tree[$id]['children'] = array();

}

// set created children

$node['children'] = $tree[$id]['children'];

// add node to array

$tree[$id] = $node;

// set parsed node as child of its parent

$tree[$node['parent_id']]['children'][$node['id']] = &$tree[$id];

}

return $tree;

}

## Joao

Thanks man! I´ve checkd a 100 other solutions and this one rocks!

## Alex Chuev

My solution:

function array_tree($array, $id = 'id', $parent_id = 'parent_id', $children = 'children') {

$tree = [[$children => []]];

$references = [&$tree[0]];

foreach($array as $item) {

if(isset($references[$item[$id]])) {

$item[$children] = $references[$item[$id]][$children];

}

$references[$item[$parent_id]][$children][] = $item;

$references[$item[$id]] =& $references[$item[$parent_id]][$children][count($references[$item[$parent_id]][$children]) - 1];

}

return $tree[0][$children];

}

## Alex Chuev

The previous code does not require ID in array indexes...