CakePHP and Tree structures

Some of you might alread have worked with the TreeBehavior to generate nested categories or something like that.
In most cases we just want to have two or three levels and some hierarchic structure using parent_id.
But trees can do way more than that. At least if you also use lft and rght (which the behavior uses internally to order the tree) and MPTT (Modified Preorder Tree Traversal).

Unfortunately, a helper for tree-structered output is not a pat of the cake core. Luckily some skilled developer(s) created a very nicely working version for 1.x which I upgraded and enhanced for 2.x.
It works flawlessly with any model that uses the TreeBehavior.

What for?

Navigation, Category Tree in Shop Systems, Threaded Boards with Posts or Comments, … The list where you can use models that behave like trees is endless.
In my case we needed a complex category tree including "active path" feature and breadcrumbs. Also some additional magic to keep the tree in a visible "length" (to only show the revelant branches and only to a specific level).

Setup

As always with plugins, the Tools plugin needs to be copied/cloned in your APP/Plugin folder and loaded via CakePlugin::loadAll(), for example.

The core behavior can just be attached to the model itself using $actsAs = array('Tree'), as documented. The helper we include in our controller as $helpers = array('Tools.Tree');.

Your table should have "parent_id", "lft", "rght" fields. If you use UUIDs, make sure that "parent_id" is UUID (char36) just as your primary key. "lft"/"rght" must be integers, though. Otherwise your tree will always be invalid as those fields have nothing to do with the ids itself, but the order inside the tree.

From the documentation: "The parent field must be able to have a NULL value! It might seem to work, if you just give the top elements a parent value of zero, but reordering the tree (and possible other operations) will fail".

Usage

TreeBehavior

I don’t want to go into the details regarding the core Tree behavior, as it is already very well explained in the documentation.

Just remember: Do not touch the lft/rght fields. They should not be in your forms or be modified from you in any way. The behavior internally sets the right values here. You just need to tell it what parent_id you want to put it under.

If you already saved some records in your tree there are usually three ways of getting the data in a way that you can output it properly:

  1. find(all) in combination with 'order' => array('lft' => 'ASC') and maybe scope/conditions
  2. find(threaded) and 'conditions' => array('id' => $id, ...) and 'order' => array('lft' => 'ASC')
  3. children($id) if you have multiple trees in your table, for example – or if you want to retrieve only a part of the tree

The last two methods will already nest your data using parent_id/children as key. The first one you can nest yourself if needed using Hash::nest() as shown below.

Note that you must set the order yourself for both find() calls. Only children() will automatically use the correct order.

Short reference of useful behavior methods:

  • getPath: return current path to this id
  • children: get all children to an id
  • removeFromTree (with true/false to remove children or moving them up)
  • moveUp
  • moveDown
  • verify: check that the tree is valid
  • recover: if not valid, try to repair the tree (with mode return/delete)

You can put two up/down icons in your index table or threaded tree list pointing to two actions up/down which then invoke the behavior’s methods.
This way you can easily sort your tree using those methods from the backend. You can also use some more sophisticated ajax dynamic tree reordering using jquery plugins etc. Then you would probably use reorder() as this method can reorder multiple items at once.

The current path is needed to build a breadcrumbs list. See the chapter for breadcrumbs below for details.

Another useful method (even though it shouldn’t be in the behavior but the view scope) is generateTreeList(). We can use it to populate our select boxes.
A baked edit/add form for your categories should look like this:

...
echo $this->Form->input('parent_id');
...

It is wise to allow "empty values", though, if the element can be a root element (or if there aren’t any tree elements yet):

echo $this->Form->input('parent_id', array('empty' => true)); // or 'empty' => ' - root element - ' etc

Just pass down $parents in your action:

$spacer = '--';
$parents = $this->Category->generateTreeList($conditions, $keyPath, $valuePath, $spacer);
$this->set(compact('parents'));

TreeHelper

Way more interesting is how we can actually output the tree in a way that allows us to style it – especially the currently active path. Also how to fully customize each tree level.

The most simple use case – using the key/value (id and name usually) of the threaded array:

// in your view/element ctp 
echo $this->Tree->generate($categories, array('id' => 'my-tree'));

I will simply output a nested ul/li tree with the displayField (name) text.

We could also use helper callbacks (here a custom MyTreeOutputHelper::format() method) to adjust the nodes:

echo $this->Tree->generate($categories, array('id' => 'my-tree', 'callback' => array($this->MyTreeOutput, 'format')));

This method then can look like:

public function format($data) {
    if (empty($data['data']['Category']['visible'])) {
        return; // do not display
    }
    // append (active) for active path elements
    return $data['data']['Category']['name'] . ($data['activePathElement'] ? ' (active)' : '');
}

A more verbose example of the tree helper capabilities using elements:

$categories = Hash::nest($categories); // optional, if you used find(all) instead of find(threaded) or children()

$treeOptions = array('id' => 'main-navigation', 'model' => 'Category', 'element' => 'node', 'autoPath' => array($currentCategory['Category']['lft'], $currentCategory['Category']['rght']));

echo $this->Tree->generate($categories, $treeOptions);

And the /Elements/node.ctp, for example:

$category = $data['Category'];
if (!$category['active']) { // You can do anything here depending on the record content
    return;
}
echo $this->Html->link($category['name'], array('action' => 'find', 'category_id' => $category['id']));

Using autoPath we can make the tree leverage the lft/rght MPTT and automatically mark the current path as active. Styling it via css is then a piece of cake.

To enhance it further, you can use frontend js via jquery plugins (accordion or multi-level menu) or the quite powerful superfish script. If you want to divide your tree in a main top and a sub side navigation you can achieve that using the maxDepth option and only return and output specific levels of the tree per menu.

Tip: Take a look at the test cases for the helper for further details on the above options and its usage as well as the expected output for those.

Short reference for the more important settings:

  • ‘model’ => name of the model (key) to look for in the data array. defaults to the first model for the current controller. If set to false 2d arrays will be allowed/expected.
  • ‘alias’ => the array key to output for a simple ul (not used if element or callback is specified)
  • ‘type’ => type of output defaults to ul
  • ‘itemType => type of item output default to li
  • ‘id’ => id for top level ‘type’
  • ‘class’ => class for top level ‘type’
  • ‘element’ => path to an element to render to get node contents.
  • ‘callback’ => callback to use to get node contents. e.g. array(&$anObject, ‘methodName’) or ‘floatingMethod’
  • ‘autoPath’ => array($left, $right [$classToAdd = ‘active’]) if set any item in the path will have the class $classToAdd added. MPTT only.
  • ‘maxDepth’ => used to control the depth upto which to generate tree
  • ‘splitCount’ => the number of "parallel" types. defaults to null (disabled) set the splitCount, and optionally set the splitDepth to get parallel lists

And internally (on top of the above settings) in callbacks and elements the following information passed in as array (callback) or variables (element) is available:

  • ‘data’ => the data array itself
  • ‘depth’
  • ‘hasChildren’
  • ‘numberOfDirectChildren’
  • ‘numberOfTotalChildren’
  • ‘firstChild’
  • ‘lastChild’
  • ‘hasVisibleChildren’
  • ‘activePathElement’

Performance

Don’t forget to add some indexes on your tables to speed up the "reading" process. This is most likely the bottle neck of larger trees.
Therefore you should add indexes for parent_id, lft and rght:

ALTER TABLE  `categories` ADD INDEX  `lft` (  `lft` );
ALTER TABLE  `categories` ADD INDEX  `rght` (  `rght` );
ALTER TABLE  `categories` ADD INDEX  `parent_id` (  `parent_id` );

Breadcrumbs

We can use the behavior’s method for this as mentioned above:

// controller
$treePath = $this->Model->getPath($currentCategoryId);
$this->set(compact('treePath'));

Now we just have to display the list and style it:

$total = count($treePath);
echo '<ul id="category-breadcrumbs" class="breadcrumbs">';
echo '<li>';
echo $this->Html->link('ALL', array('action'=>'find', 'category_id' => ''));
echo '</li>';
foreach ($treePath as $key => $treeCategory) {
    if (!$treeCategory['Category']['active']) {
        continue;
    }
    echo '<li>';
    if ($total === $key + 1) {
        echo h($treeCategory['Category']['name']);
    } else {
        echo $this->Html->link($treeCategory['Category']['name'], array('action'=>'find', 'category_id' => $treeCategory['Category']['id']));
    }
    echo '</li>';
}
echo '</ul>';
}

You will notice that the last element will not be a link anymore but a normal <li> tag. This way we can style it as the current (active) node in a different way to the other path elements.

Tip: You could also use the existing helper method addCrumb() as well as getCrumbList() of the HtmlHelper and output your breadcrumbs this way. If you don’t need any special treatment of your nodes, that is.

More experimental stuff

For very large trees like in category navigation structures with >> 100 category nodes it probably makes sense to only display the current level, and all direct siblings in the "active path". It can also be a factor for search engines to only link the "relevant" cross-links here.
I experimented with the hideUnrelated option and a custom callback or element to manually hide the elements marked as 'hide' => true.

Tip: It does need a nested structure (so make sure you use the right methods from above) and the threePath passed in as option. See the test case for details.

The following keys are then also available in callbacks/elements:

  • show => if it has to be shown as part of the active path
  • parent_show => if it is a child of an active path element and should also be visible
  • hide => if it should be hidden (tops the other two settings)

Yet undecided

I have been thinking about removing the find(all) support in favor of supporting always nested array input. This would probably make the code way shorter and easier to read and maintain. As outlined above using Hash::nest() you can always form your array this way prior to passing it into the helper. So the overhead here could be removed.

Feel free to submit any ideas, criticism or PRs (pull requests). I just recently started to seriously work with tree structured data.

CakePHP 3.x

The helper has been upgraded to work with the new major version and both entities as array or objects directly.
Note that you need to use a custom finder now to retrieve the data:

$list = $categories->find('treeList', ['spacer' => ...]); // generateTreeList() does not exist anymore

The same for children() and getPath(): They are find('children') and find('path').

Using the Shim plugin you already use the same custom finders in 2.x, as well – making the upgrade to 3.x then smoother in the future.

Note that one important change in the DB structure from 2.x to 3.x is that the lft/rght fields cannot be unsigned anymore:

  • lft (integer, signed) Used to maintain the tree structure
  • rght (integer, signed) Used to maintain the tree structure

Those can now also be negative values for some performance gain.

For details on 3.x, see the docs.

4.56 avg. rating (91% score) - 16 votes

38 Comments

  1. Nice article. I just integrated a cake tree with ajax + jquery ui so as to allow the tree nodes to be moved for a clients custom CMS . It was quite tricky! usually these trees "Sorting" are done by serializing the whole tree and sending that bakc after a move occurs (or on a Submit press). Howver the cake tree built-in methods don’t have a fromSerialize() method, so I made it work with the delta facility . The core cake tree is excellent though otherwise and keeps everytthing underneath organized.

  2. Do you think it would be worth adding the fromSerialize() etc as core feature? Or is it too app specific and not worth being generalized?

    Maybe you want to ouline what you did and how you got this working. Might be interesting for others, as well.

  3. Real big thnx, i spent 2 days to learn how to make catalog menu in best way, ur article helps me on 100%. Keep doing this work for all of us 🙂

  4. The previous code example can be tweaked to perform a bottom-up (postorder, leaf to root) traversal. This traversal can be used to, for example, delete nodes of a subtree from bottom to top.

  5. Hello,

    As yo can see with the code above, on some "internal" li and ul, I need to add a class, is this possible ?

    <a href="http://www.example.com/" rel="nofollow">Contact</a>
    <a href="http://www.example.com/" rel="nofollow">Services</a>
        
    <a href="http://www.example.com/" rel="nofollow">Service 1</a>
        <a href="http://www.example.com/" rel="nofollow">Service 1.1</a>
        <a href="http://www.example.com/" rel="nofollow">Service 1.2</a>
                    
    <a href="http://www.example.com/" rel="nofollow">Service 2</a>
    <a href="http://www.example.com/" rel="nofollow">Service 3</a>
    <a href="http://www.example.com/" rel="nofollow">Service 4</a>
    <a href="http://www.example.com/" rel="nofollow">Service 5</a>
        
    <a href="http://www.example.com/" rel="nofollow">Help</a>

    Thanks

  6. Everything is possible, for some special things you need the custom callback functionality then, though.

  7. Ok, thanks for the answer.
    For those of you with the same question, here is the solution:

    1. I used an element
    2. In this element I used this code to add a class="dropdown" on all my ul :
    $this->Tree->addTypeAttribute('class', 'dropdown');
    1. I used this other code to add a class="has-dropdown" only on LI with children :
    if (isset($numberOfTotalChildren) && $numberOfTotalChildren > 0) {
        $this->Tree->addItemAttribute('class', 'has-dropdown');
    }

    Thanks for the help and the code !

  8. Not new to cakephp but new to the treehelper – thanks for this code. Just a question. Apart from just displaying the ‘name’ column of my table, I would also like to display some additional columns as well as some linked items (edit current item, for example). Any suggestions on how to do this? You cannot mix the ordered list with a table, for example …

  9. Use either callbacks or the custom element to inject anything you want into it. It can be a div or span tag including all the information you need.

  10. Thanks, I have only started to look at this again today – I am still stuck with styling these. I have used the element but the problem is that the nodes display still does not want to go where I want it to
    I have the scenario where I have :

    display some related table stuff to the tree

    Display the tree belonging to the stuff in the row above

    But the tree helper and node element takes the tree view completely OUT OF the table and displays it outside the table, ABOVE the table in fact.
    How can I get the tree to display where I want it to display!

  11. Aarrgghh…. nevermind… had an extra closing td where I wasn’t supposed to have one (blush). Please ignore..

  12. Hi,

    Unfortunately I end up with this error when calling the Tree Helper :

    Notice (8): Undefined index: name [APP/View/Helper/TreeHelper.php, line 273]

    Which is : $content = $row[$alias];

    Any idea or leads ?

    Thanks

  13. Brilliant tutorial. Thanks for uploading this. Its just a Tree helper that I’m after, something to help with converting the array to HTML but I’ll look into that tools plugin. Why not add a tree component to the Tools plugin? I’ve already started one myself, I can give you the code. The component I made basically returns conditions you need to select items joined to the tree table through a relational table, you just plug the category ID into it, and it will get you all the items in that category, and in all subcategories.

  14. Hi,

    I have a problem with the view when i generate tree.

    He says "Invalid Tree Structure"
    What kind of structure is necessary

  15. Debug the helper and find out where it throws this error. Then see what the condition is that leads to it.

    Tip: The blog post above does tell you what the format should be like.. "The last two methods will already nest your data using parent_id/children as key. The first one you can nest yourself if needed using Hash::nest() as shown below"

  16. Oh thks !!
    They are API Doc ??
    Because i want to use callback to style the tree in menu :

                          	<a href="#" rel="nofollow">Maison</a>					
                                        <a href="#" rel="nofollow">Bricolage</a>
                                            <a href="#" rel="nofollow">Droguerie</a>
                                                <a href="#" rel="nofollow">Outils</a>
                                                    <a href="#" rel="nofollow">Perçeuse</a>
                                                        <a href="#" rel="nofollow">Tourne vis</a>
                                                            <a href="#" rel="nofollow">Crusiforme</a>
                                                                <a href="#" rel="nofollow">Plat</a>
                                                                    <a href="#" rel="nofollow">Taille 8</a>
                                                                        <a href="#" rel="nofollow">Grande taille</a>
                                                                            <a href="#" rel="nofollow">Taille 24</a>
                                                                            <a href="#" rel="nofollow">Taille 25</a>
                                            <a href="#" rel="nofollow">Peinture écologique</a>
                                        <a href="#" rel="nofollow">Bureau et fournitures</a>
                                            <a href="#" rel="nofollow">Accessoires de bureau</a>											
                                                    <a href="#" rel="nofollow">Calculatrice</a>
                                                    <a href="#" rel="nofollow">Stylo</a>
                                            <a href="#" rel="nofollow">Éclairages de bureau</a>
                                    <a href="#" rel="nofollow">Chambre</a>
                                    <a href="#" rel="nofollow">Décoration</a>
                                        <a href="#" rel="nofollow">Livres</a>									
                                            <a href="#" rel="nofollow">Gestion quotidiennes</a>
                                                <a href="#" rel="nofollow">Geste de l'eau</a>
                                                    <a href="#" rel="nofollow">Eau de pluie</a>
                                                    <a href="#" rel="nofollow">Récupération</a>
                                            <a href="#" rel="nofollow">Cameras</a>
                        <a href="#" rel="nofollow">Plein air</a>
  17. Sorry for this block, i have found a solution, but it’s possible to put the category in a link

    <a href="#" rel="nofollow">test</a>
  18. @Chrill,

    As described in this article, by using an element you can do what you want on and with your content.

    Bye,
    Hervé

  19. Hello Mark,

    Your helper works perfectly. I just wonder if there is a way to output something like this with a callback.

    That is to say: can I change UL’s classes dynamically, according to the depth of the element? Can you provide a short example?

        <a href="#" rel="nofollow">Widgets</a>
        <a href="#" rel="nofollow">Calendar</a>
        <a href="#" rel="nofollow">Fonts</a>
        <a href="#" rel="nofollow">Font Awesome</a>
        
            <a>Pages <i></i></a>
            
                <a href="#" rel="nofollow"><i></i> Blank</a>
                <a href="#" rel="nofollow"><i></i> Login</a>
                <a href="#" rel="nofollow"><i></i> Contact</a>
  20. Of course you can 🙂
    The depth is provided in the callback/element.
    And upon that you can dynamically switch to any class you want to.

  21. when i use this
    echo $this-&gt;Form-&gt;input(‘parent_id’, array(’empty’ =&gt; true)); then all data is shown in drop-dowm nemu.
    But whe I use
    echo $this-&gt;Tree-&gt;generate($parents, array(‘id’ =&gt; ‘my-tree’));
    then error occurs given below. kindly help me in this issue.

    Error: Cannot create references to/from string offsets nor overloaded objects

    File:C:\xampp\htdocs\website\app\Plugin\Tools\View\Helper\TreeHelper.php
    Line: 173

  22. i’m showing data in index.ctp
    this shown fine drop down menu with data
    echo $this -&gt; Form -&gt; input(‘parent_id’, array(’empty’ =&gt; true));

    But when I use
    echo $this -&gt; Tree -&gt; generate($parents, array(‘id’ =&gt; ‘my-tree’));

    it generates error. which are

    Error: Cannot create references to/from string offsets nor overloaded objects

    File:C:\xampp\htdocs\website\app\Plugin\Tools\View\Helper\TreeHelper.php

  23. Do not use the Tree helper to output list data.
    The data given to the helper needs to be a non flat array as documented – not find(list) or generateTreeList(), but find(all/threaded) etc.

  24. first of all , sorry for first 2 comments, went wrong. Now i come to the point, Following code shows data in drop down menu in index.ctp, that fine.

    echo $this->Form->input('parent_id', array('empty' => true));
    .

    but when i tried to use

    echo $this->Tree->generate($parents, array('id' => 'my-tree'));
    .

    This generates error
    which are
    Error: Cannot create references to/from string offsets nor overloaded objects

    File:C:\xampp\htdocs\website\app\Plugin\Tools\View\Helper\TreeHelper.php

  25. I’m using this in controller , index action

      $spacer = '--';
    $parents = $this->Category->generateTreeList(null, null, null, $spacer);
    $this->set(compact('parents'));
  26. thanks , i got it . now data is displayed fine. bundle of thanks. now i will move forward to use rest of the functionalities . thanks again

  27. I want to add functionality on categories to show-hide sub-categories. On loading only main category should be visible, when user will click on category then sub-categories should be displayed. I just want to know either this functionality is being provided by ToolTree helper or i would be required to write code for this ?

  28. Hi,
    How to pass custom parameter to element when i use ‘element’ key in array for $this-&gt;Tree-&gt;generate()?
    Thank you!

  29. @kuskov,

    Try something like this :

    $treeOptions = array(
        'id' => '',
        'class' => 'nav navbar-nav',
        'alias' => 'title',
        'model' => 'Menu',
        'element' => 'node_main_menu',
    );
    $this->Tree->addTypeAttribute('class', 'dropdown');
    $this->Tree->addItemAttribute('class', 'dropdown');
    echo $this->Tree->generate($mainMenu, $treeOptions);
  30. Hi Mark, this is awesome article &amp; I learnt a lot from it. Here is a question:
    I am trying to add a class = "nav" to all the but failed. I tried
    $this-&gt;Tree-&gt;addTypeAttribute(‘class’, ‘nav’);
    in the element &amp; callback.
    Nothing works.
    Is there any way if I do not want to use JS to do this?
    Thank you.

  31. thank for sharing
    now i want to show tree or binary tree with graphics
    ex: How use foreach to loop and draw as bellow?
    MemberA
    / |
    MemberB MemberC

  32. Hello Mark

    Could you help me to understand the usage of autoPath?

    I had to set the model (even being the default one) but nothing happened. No ‘active’ class was added.

    Do you have an example for this usage?

    I’m using a find(all) with the Hash::nest($categories); and a $this-&gt;Tree-&gt;generate with a element to customize the HTML.

    I know that this is maybe a little thing that I did wrong, but I couldn’t find the problem.

    Thanks in advanced

  33. Please take a look at the test cases, there should be an example.
    But actually, the post above contains such an example @ "A more verbose example of the tree helper capabilities using elements:"
    Take a 2nd look.
    It requires the lft and rght value of a specific record and this will then identify this record as the active path element.

  34. I have a large data tree, I would like to display the branch that is active. Would it be possible to use this helper when clicking on a branch so that the branch will be delivered by Ajax? I assume that the click button would only be there if the branch contained other sub-branches. Please advise, thank you

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.