Overview

Hierarchical (i.e. Tree structured) data is usually stored and accessed using the Adjacency List Model: It is easy to understand, and the code is simple.

However, it is slow and inefficient due to the recursion which requires a database query for each node in the tree. As the name suggests, the numbering follows from a preorder (depth-first) traversal of the the resulting tree.

A more efficient and flexible, albeit less straightforward, approach is the so called, Modified Preorder Tree Traversal. In this method, rather than storing the parent of each node, a left and right value is stored for each node, as illustrated in the diagram.

In this article, we coerce EasyTree to implement the Modified Preorder Tree Traversal method. It's considerably more ambitions and realistic than our previous introduction.

TL;DR There is a working example at the bottom of the page!

Database Representation

Fetch the data

First we need to fetch the data. We do this on the server using PHP and MySQL.

In general, we can fetch the subtree for any node:

$node = ...;
$sql = "SELECT * FROM tree WHERE lft BETWEEN {$node['lft']} AND {$node['rgt']} ORDER BY lft ASC;";
// call the database, following assumes codeignitor
$nodes = $query = $this->db->query($sql)->result_array();

But we will usually grab the whole tree, which is much simpler:

$nodes = $this->db
    ->query("SELECT * FROM tree ORDER BY lft ASC;")
    ->result_array();

In either case, it is critical that it is ordered by the lft column for the following procedure to work!

By the way, the above code should go into your model in an MVC architecture.

Convert data to a nested <ul>

Again, we are working with PHP on the server for this.

Notice, that the code is intended to run right in a view, inside the enclosing <ul>. . .</ul>. If the tree is empty, you'll get an empty list.

<ul>
<?php
    function entry($row) {
        $icon = '<i class="icon-'.$row['icon'].'"></i> ';
        return $icon.'<i class="lft">'.$row['lft'].'</i> <b>'.$row['title'].'</b> <i class="rgt">'.$row['rgt'].'</i>';
        }
    $stack = [];

    // display each row
    foreach($nodes as $row) {
        if (count($stack)>0) { // only check stack if there is one

            // check if we should remove a node from the stack
            while ($stack[count($stack)-1] < $row['lft']) {
                $deb.=' '.array_pop($stack);
                echo '</ul></li>'.PHP_EOL;
                }
            }

        // display indented node
        $hasChildren = $row['rgt'] - $row['lft'] > 1;
        $attrs = 'lft="'.$row['lft'].'" rgt="'.$row['rgt'].'"'
                .' node-id="'.$row['id'].'"'
                .' title="'.$row['lead'].'"';
        $name = entry($row);
        echo "<li $attrs>".$name;
        if ($hasChildren) { // if node has kids
            echo '<ul>'.PHP_EOL;
            $stack[] = $row['rgt']; // add this node to the stack
            }
        else echo '</li>'.PHP_EOL;
        }

    while (count($stack)) {
        array_pop($stack);
        echo '</ul></li>'.PHP_EOL;
        }
?>
</ul>

Client Side

Now that the view has built the tree as a <ul>, we call easytree to wrap this list

    easytree = $('#demo_tree')
        .on('click', 'span.easytree-node', function(e) {
            var id = $(this).attr('id');
            _actNode = easytree.getNode(id);
            updateWhiteboard('clicked: ' + _actNode.text);
            showDetails(_actNode);
            return false;
            })
        .easytree({
            enableDnd: true,
            openLazyNode: openLazyNode,
            canDrop: canDrop,
            dropping: dropping,
            dropped: dropped
            });

Easytree is built on jQuery, so we can chain the call to easytree() on line 9, after setting up an event handler beginning on line 2.

This event handler selects the node that is clicked.

The rest of the client code is fairly straight forward — just right click this page and select View Source to read the code: It is documented. Here are a few tips:

• The easytree id is id-lft-rgt
• add and delete work, but DND needs work
  • call rebuild() to recalc tree
• We update the node's lft and rgt locally, but not on the server
• Also check the console log

And now here is the

Working Example!