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 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.

Read more from the Software engineering category