Modified Preorder Tree Traversal

README.md

Modified Preorder Tree Traversal

Hierarchical data metrics that allows fast read operations on tree like structures.

Based on Left and Right fields that are set during tree traversal. When entered into node value is set to it's Left, when exiting node value is set to it's Right.

Sample implementation

Usual related queries are

Get all children including specified node

SELECT * FROM table
WHERE Lft>=specified.Lft AND Rgt<=specified.Rgt

Get all children w/out specified node

SELECT * FROM table
WHERE Lft>specified.Lft AND Rgt<specified.Rgt

Get all parents including specified node from specified node to root

SELECT * FROM table
WHERE Lft<=specified.Lft AND Rgt>=specified.Rgt
ORDER BY Lft DESC

Get all parents w/out specified node from root to specified node

SELECT * FROM table
WHERE Lft<specified.Lft AND Rgt>specified.Rgt
ORDER BY Lft ASC

Details

Taken from http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
There was similar mysql tech article, but disappeared. Copied this here to gist to be sure I could find it always.

Introduction

Most users at one time or another have dealt with hierarchical data in a SQL database and no doubt learned that the management of hierarchical data is not what a relational database is intended for. The tables of a relational database are not hierarchical (like XML), but are simply a flat list. Hierarchical data has a parent-child relationship that is not naturally represented in a relational database table.

For our purposes, hierarchical data is a collection of data where each item has a single parent and zero or more children (with the exception of the root item, which has no parent). Hierarchical data can be found in a variety of database applications, including forum and mailing list threads, business organization charts, content management categories, and product categories. For our purposes we will use the following product category hierarchy from an fictional electronics store:

These categories form a hierarchy in much the same way as the other examples cited above. In this article we will examine two models for dealing with hierarchical data in MySQL, starting with the traditional adjacency list model.

The Adjacency List Model

Typically the example categories shown above will be stored in a table like the following (I'm including full CREATE and INSERT statements so you can follow along):

CREATE TABLE category(
    category_id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(20) NOT NULL,
    parent INT DEFAULT NULL
);


INSERT INTO category VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),
    (3,'TUBE',2),(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
    (7,'MP3 PLAYERS',6),(8,'FLASH',7),(9,'CD PLAYERS',6),
    (10,'2 WAY RADIOS',6);

SELECT * FROM category ORDER BY category_id;

+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+
10 rows in set (0.00 sec)

In the adjacency list model, each item in the table contains a pointer to its parent. The topmost element, in this case electronics, has a NULL value for its parent. The adjacency list model has the advantage of being quite simple, it is easy to see thatFLASH is a child ofmp3 players, which is a child of portable electronics, which is a child of electronics. While the adjacency list model can be dealt with fairly easily in client-side code, working with the model can be more problematic in pure SQL.

Retrieving a Full Tree

The first common task when dealing with hierarchical data is the display of the entire tree, usually with some form of indentation. The most common way of doing this is in pure SQL is through the use of a self-join:

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

+-------------+----------------------+--------------+-------+
| lev1        | lev2                 | lev3         | lev4  |
+-------------+----------------------+--------------+-------+
| ELECTRONICS | TELEVISIONS          | TUBE         | NULL  |
| ELECTRONICS | TELEVISIONS          | LCD          | NULL  |
| ELECTRONICS | TELEVISIONS          | PLASMA       | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS  | FLASH |
| ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS   | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL  |
+-------------+----------------------+--------------+-------+
6 rows in set (0.00 sec)

Finding all the Leaf Nodes

We can find all the leaf nodes in our tree (those with no children) by using a LEFT JOIN query:

SELECT t1.name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;

+--------------+
| name         |
+--------------+
| TUBE         |
| LCD          |
| PLASMA       |
| FLASH        |
| CD PLAYERS   |
| 2 WAY RADIOS |
+--------------+

Retrieving a Single Path

The self-join also allows us to see the full path through our hierarchies:

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';

+-------------+----------------------+-------------+-------+
| lev1        | lev2                 | lev3        | lev4  |
+-------------+----------------------+-------------+-------+
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |
+-------------+----------------------+-------------+-------+
1 row in set (0.01 sec)

The main limitation of such an approach is that you need one self-join for every level in the hierarchy, and performance will naturally degrade with each level added as the joining grows in complexity.

Limitations of the Adjacency List Model

Working with the adjacency list model in pure SQL can be difficult at best. Before being able to see the full path of a category we have to know the level at which it resides. In addition, special care must be taken when deleting nodes because of the potential for orphaning an entire sub-tree in the process (delete the portable electronics category and all of its children are orphaned). Some of these limitations can be addressed through the use of client-side code or stored procedures. With a procedural language we can start at the bottom of the tree and iterate upwards to return the full tree or a single path. We can also use procedural programming to delete nodes without orphaning entire sub-trees by promoting one child element and re-ordering the remaining children to point to the new parent.

The Nested Set Model

What I would like to focus on in this article is a different approach, commonly referred to as the Nested Set Model. In the Nested Set Model, we can look at our hierarchy in a new way, not as nodes and lines, but as nested containers. Try picturing our electronics categories this way:

Notice how our hierarchy is still maintained, as parent categories envelop their children.We represent this form of hierarchy in a table through the use of left and right values to represent the nesting of our nodes:

CREATE TABLE nested_category (
    category_id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(20) NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

INSERT INTO nested_category VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),
  (3,'TUBE',3,4),(4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),
  (7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),(9,'CD PLAYERS',15,16),
  (10,'2 WAY RADIOS',17,18);

SELECT * FROM nested_category ORDER BY category_id;

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

We use lft and rgt because left and right are reserved words in MySQL, see http://dev.mysql.com/doc/mysql/en/reserved-words.html for the full list of reserved words.

So how do we determine left and right values? We start numbering at the leftmost side of the outer node and continue to the right:

This design can be applied to a typical tree as well:

When working with a tree, we work from left to right, one layer at a time, descending to each node's children before assigning a right-hand number and moving on to the right. This approach is called the modified preorder tree traversal algorithm.

Retrieving a Full Tree

We can retrieve the full tree through the use of a self-join that links parents with nodes on the basis that a node's lft value will always appear between its parent's lft and rgt values:

SELECT node.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;

+----------------------+
| name                 |
+----------------------+
| ELECTRONICS          |
| TELEVISIONS          |
| TUBE                 |
| LCD                  |
| PLASMA               |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS          |
| FLASH                |
| CD PLAYERS           |
| 2 WAY RADIOS         |
+----------------------+

Unlike our previous examples with the adjacency list model, this query will work regardless of the depth of the tree. We do not concern ourselves with the rgt value of the node in our BETWEEN clause because the rgt value will always fall within the same parent as the lft values.

Finding all the Leaf Nodes

Finding all leaf nodes in the nested set model even simpler than the LEFT JOIN method used in the adjacency list model. If you look at the nested_category table, you may notice that the lft and rgt values for leaf nodes are consecutive numbers. To find the leaf nodes, we look for nodes where rgt = lft + 1:

SELECT name
FROM nested_category
WHERE rgt = lft + 1;

+--------------+
| name         |
+--------------+
| TUBE         |
| LCD          |
| PLASMA       |
| FLASH        |
| CD PLAYERS   |
| 2 WAY RADIOS |
+--------------+

Retrieving a Single Path

With the nested set model, we can retrieve a single path without having multiple self-joins:

SELECT parent.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'FLASH'
ORDER BY node.lft;

+----------------------+
| name                 |
+----------------------+
| ELECTRONICS          |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS          |
| FLASH                |
+----------------------+

Finding the Depth of the Nodes

We have already looked at how to show the entire tree, but what if we want to also show the depth of each node in the tree, to better identify how each node fits in the hierarchy? This can be done by adding a COUNT function and a GROUP BY clause to our existing query for showing the entire tree:

SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| ELECTRONICS          |     0 |
| TELEVISIONS          |     1 |
| TUBE                 |     2 |
| LCD                  |     2 |
| PLASMA               |     2 |
| PORTABLE ELECTRONICS |     1 |
| MP3 PLAYERS          |     2 |
| FLASH                |     3 |
| CD PLAYERS           |     2 |
| 2 WAY RADIOS         |     2 |
+----------------------+-------+

We can use the depth value to indent our category names with the CONCAT and REPEAT string functions:

SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+-----------------------+
| name                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  PORTABLE ELECTRONICS |
|   MP3 PLAYERS         |
|    FLASH              |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
+-----------------------+

Of course, in a client-side application you will be more likely to use the depth value directly to display your hierarchy. Web developers could loop through the tree, adding

and

tags as the depth number increases and decreases.

Depth of a Sub-Tree

When we need depth information for a sub-tree, we cannot limit either the node or parent tables in our self-join because it will corrupt our results. Instead, we add a third self-join, along with a sub-query to determine the depth that will be the new starting point for our sub-tree:

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| PORTABLE ELECTRONICS |     0 |
| MP3 PLAYERS          |     1 |
| FLASH                |     2 |
| CD PLAYERS           |     1 |
| 2 WAY RADIOS         |     1 |
+----------------------+-------+

This function can be used with any node name, including the root node. The depth values are always relative to the named node.

Find the Immediate Subordinates of a Node

Imagine you are showing a category of electronics products on a retailer web site. When a user clicks on a category, you would want to show the products of that category, as well as list its immediate sub-categories, but not the entire tree of categories beneath it. For this, we need to show the node and its immediate sub-nodes, but no further down the tree. For example, when showing the PORTABLE ELECTRONICS category, we will want to show MP3 PLAYERS, CD PLAYERS, and 2 WAY RADIOS, but not FLASH.

This can be easily accomplished by adding a HAVING clause to our previous query:

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                        nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                        AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| PORTABLE ELECTRONICS |     0 |
| MP3 PLAYERS          |     1 |
| CD PLAYERS           |     1 |
| 2 WAY RADIOS         |     1 |
+----------------------+-------+

If you do not wish to show the parent node, change the HAVING depth <= 1 line to HAVING depth = 1.

Aggregate Functions in a Nested Set

Let's add a table of products that we can use to demonstrate aggregate functions with:

CREATE TABLE product
(
        product_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(40),
        category_id INT NOT NULL
);

INSERT INTO product(name, category_id) VALUES('20" TV',3),('36" TV',3),
('Super-LCD 42"',4),('Ultra-Plasma 62"',5),('Value Plasma 38"',5),
('Power-MP3 5gb',7),('Super-Player 1gb',8),('Porta CD',9),('CD To go!',9),
('Family Talk 360',10);

SELECT * FROM product;

+------------+-------------------+-------------+
| product_id | name              | category_id |
+------------+-------------------+-------------+
|          1 | 20" TV            |           3 |
|          2 | 36" TV            |           3 |
|          3 | Super-LCD 42"     |           4 |
|          4 | Ultra-Plasma 62"  |           5 |
|          5 | Value Plasma 38"  |           5 |
|          6 | Power-MP3 128mb   |           7 |
|          7 | Super-Shuffle 1gb |           8 |
|          8 | Porta CD          |           9 |
|          9 | CD To go!         |           9 |
|         10 | Family Talk 360   |          10 |
+------------+-------------------+-------------+

Now let's produce a query that can retrieve our category tree, along with a product count for each category:

SELECT parent.name, COUNT(product.name)
FROM nested_category AS node ,
        nested_category AS parent,
        product
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.category_id = product.category_id
GROUP BY parent.name
ORDER BY node.lft;

+----------------------+---------------------+
| name                 | COUNT(product.name) |
+----------------------+---------------------+
| ELECTRONICS          |                  10 |
| TELEVISIONS          |                   5 |
| TUBE                 |                   2 |
| LCD                  |                   1 |
| PLASMA               |                   2 |
| PORTABLE ELECTRONICS |                   5 |
| MP3 PLAYERS          |                   2 |
| FLASH                |                   1 |
| CD PLAYERS           |                   2 |
| 2 WAY RADIOS         |                   1 |
+----------------------+---------------------+

This is our typical whole tree query with a COUNT and GROUP BY added, along with a reference to the product table and a join between the node and product table in the WHERE clause. As you can see, there is a count for each category and the count of subcategories is reflected in the parent categories.

Adding New Nodes

Now that we have learned how to query our tree, we should take a look at how to update our tree by adding a new node. Let's look at our nested set diagram again:

If we wanted to add a new node between the TELEVISIONS and PORTABLE ELECTRONICS nodes, the new node would have lft and rgt values of 10 and 11, and all nodes to its right would have their lft and rgt values increased by two. We would then add the new node with the appropriate lft and rgt values. While this can be done with a stored procedure in MySQL 5, I will assume for the moment that most readers are using 4.1, as it is the latest stable version, and I will isolate my queries with a LOCK TABLES statement instead:

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category
WHERE name = 'TELEVISIONS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO nested_category(name, lft, rgt)
    VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);

UNLOCK TABLES;

We can then check our nesting with our indented tree query:

SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+-----------------------+
| name                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  GAME CONSOLES        |
|  PORTABLE ELECTRONICS |
|   MP3 PLAYERS         |
|    FLASH              |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
+-----------------------+

If we instead want to add a node as a child of a node that has no existing children, we need to modify our procedure slightly. Let's add a new FRS node below the 2 WAY RADIOS node:

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft FROM nested_category

WHERE name = '2 WAY RADIOS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;

INSERT INTO nested_category(name, lft, rgt) VALUES('FRS', @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;

In this example we expand everything to the right of the left-hand number of our proud new parent node, then place the node to the right of the left-hand value. As you can see, our new node is now properly nested:

SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+-----------------------+
| name                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  GAME CONSOLES        |
|  PORTABLE ELECTRONICS |
|   MP3 PLAYERS         |
|    FLASH              |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
|    FRS                |
+-----------------------+

Deleting Nodes

The last basic task involved in working with nested sets is the removal of nodes. The course of action you take when deleting a node depends on the node's position in the hierarchy; deleting leaf nodes is easier than deleting nodes with children because we have to handle the orphaned nodes.

When deleting a leaf node, the process if just the opposite of adding a new node, we delete the node and its width from every node to its right:

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

UNLOCK TABLES;

And once again, we execute our indented tree query to confirm that our node has been deleted without corrupting the hierarchy:

SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+-----------------------+
| name                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  PORTABLE ELECTRONICS |
|   MP3 PLAYERS         |
|    FLASH              |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
|    FRS                |
+-----------------------+

This approach works equally well to delete a node and all its children:

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

UNLOCK TABLES;

And once again, we query to see that we have successfully deleted an entire sub-tree:

SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+-----------------------+
| name                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  PORTABLE ELECTRONICS |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
|    FRS                |
+-----------------------+

The other scenario we have to deal with is the deletion of a parent node but not the children. In some cases you may wish to just change the name to a placeholder until a replacement is presented, such as when a supervisor is fired. In other cases, the child nodes should all be moved up to the level of the deleted parent:

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';

DELETE FROM nested_category WHERE lft = @myLeft;

UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1
    WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;

UNLOCK TABLES;

In this case we subtract two from all elements to the right of the node (since without children it would have a width of two), and one from the nodes that are its children (to close the gap created by the loss of the parent's left value). Once again, we can confirm our elements have been promoted:

SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+---------------+
| name          |
+---------------+
| ELECTRONICS   |
|  TELEVISIONS  |
|   TUBE        |
|   LCD         |
|   PLASMA      |
|  CD PLAYERS   |
|  2 WAY RADIOS |
|   FRS         |
+---------------+

Other scenarios when deleting nodes would include promoting one of the children to the parent position and moving the child nodes under a sibling of the parent node, but for the sake of space these scenarios will not be covered in this article.

Final Thoughts

While I hope the information within this article will be of use to you, the concept of nested sets in SQL has been around for over a decade, and there is a lot of additional information available in books and on the Internet. In my opinion the most comprehensive source of information on managing hierarchical information is a book called Joe Celko's Trees and Hierarchies in SQL for Smarties, written by a very respected author in the field of advanced SQL, Joe Celko. Joe Celko is often credited with the nested sets model and is by far the most prolific author on the subject. I have found Celko's book to be an invaluable resource in my own studies and highly recommend it. The book covers advanced topics which I have not covered in this article, and provides additional methods for managing hierarchical data in addition to the Adjacency List and Nested Set models.

In the References / Resources section that follows I have listed some web resources that may be of use in your research of managing hierarchical data, including a pair of PHP related resources that include pre-built PHP libraries for handling nested sets in MySQL. Those of you who currently use the adjacency list model and would like to experiment with the nested set model will find sample code for converting between the two in the Storing Hierarchical Data in a Database resource listed below.

References / Resources

• Joe Celko's Trees and Hierarchies in SQL for Smarties - ISBN 1-55860-920-2
• Storing Hierarchical Data in a Database
• A Look at SQL Trees
• SQL Lessons
• Nontraditional Databases
• Trees in SQL
• Trees in SQL (2)
• Converting an adjacency list model to a nested set model
• Nested Sets in PHP Demonstration (German)
• A Nested Set Library in PHP

store.php

<?php
/**
 * @abstract Tree class working with Joe Celko modified preorder algorithm (Left, Right attributes)
 *
 * Legend:
 *
 * Ancestor   means any ancestor (parent, grand parent, etc.)
 * Parent     means only direct ancestor i.e. parent
 * Child      means only direct descendant
 * Descendant means any descendant (child, grand child, etc.)
 *
 * Level      means depth of node in tree
 * Root       means node at the very top of hierarchy, this node does NOT have any ancestor
 * Leaf       means any node whoch does NOT have any children
 *
 */
abstract class FW_TreeModel extends FW_Model {

    protected $dataSource;
    private static $tplStr = "{\$CONTROLLER_TABLENAME}";

    protected $tableName;
    protected $tablePkName;

    protected $tableParentColName;
    protected $tableLevelColName;

    protected $tableLeftColName;
    protected $tableRightColName;
    protected $tableTitleColName;
    protected $tableFlagColName;

    protected $extraTreeDataAttrs = array();

    public function __construct($dataSource) {
        $this->setDataSource($dataSource);
    }

    protected function setDataSource($dataSource) {
        if (is_array($dataSource)) {
            $this->dataSource = $dataSource;
            $this->tableName = $dataSource['tableName'];
            $this->tablePkName = $dataSource['pkColName'];
            $this->tableParentColName = $dataSource['parentColName'];
            $this->tableLevelColName = $dataSource['levelColName'];
            $this->tableLeftColName = $dataSource['leftColName'];
            $this->tableRightColName = $dataSource['rightColName'];
            $this->tableTitleColName = $dataSource['titleColName'];
            $this->tableFlagColName = $dataSource['flagColName'];
        }
    }

    public function addExtraTreeDataAttrs($extraTreeDataAttrs) {
        $this->extraTreeDataAttrs = $extraTreeDataAttrs;
    }

    private function resetTmpTable() {
        FW_DB::query("
            DROP TABLE IF EXISTS Master_Controller_Tmp
        ");
        FW_DB::query("
            Create table if not exists Master_Controller_Tmp (
                ControllerID Int UNSIGNED NOT NULL,
                ModuleID Smallint UNSIGNED,
                Title Varchar(64) NOT NULL,
                Path Varchar(255) NOT NULL,
                IsActive Tinyint UNSIGNED NOT NULL DEFAULT 1,
                IsExtra Tinyint UNSIGNED NOT NULL DEFAULT 0,
                ShowInMenu Tinyint UNSIGNED NOT NULL DEFAULT 1,
                LinkedControllerID Int UNSIGNED DEFAULT NULL,
                ParentControllerID Int UNSIGNED DEFAULT NULL,
                Level Tinyint(3) UNSIGNED DEFAULT 0,
                Lft Int(10) UNSIGNED DEFAULT NULL,
                Rgt Int(10) UNSIGNED DEFAULT NULL,
                Flag Tinyint UNSIGNED NOT NULL DEFAULT 0,
             Primary Key (ControllerID)) ENGINE = InnoDB;
        ");
    }

    public function updateFromDump(&$dumpStr) {
        $this->resetTmpTable();
        $queries = explode(";", $dumpStr);
        foreach ($queries as $query) {
            if (trim($query) != "") {
                $query = str_replace(self::$tplStr, "Master_Controller_Tmp", $query);
                FW_DB::query($query);
            }
        }
        $toDelete = FW_DB::getCol("SELECT mc.ControllerID
            FROM Master_Controller mc
            LEFT JOIN Master_Controller_Tmp mct ON mc.ControllerID = mct.ControllerID
            WHERE ISNULL(mct.ControllerID)");
        foreach ($queries as $query) {
            if (trim($query) != "") {
                $query = str_replace(self::$tplStr, "Master_Controller", $query);
                FW_DB::query($query);
            }
        }
        if (count($toDelete)) {
            $toDeleteStr = "(" . implode(",", $toDelete) . ")";
            FW_DB::query("DELETE FROM Master_Controller WHERE ControllerID IN $toDeleteStr ORDER By Lft DESC");
        }
    }

    /**
     * @param int|null $rootNodeID
     * @param int|null $maxLevels
     * @param bool $includeRootNode
     * @param bool $returnLeafData
     * @param bool $inversedBranchMode
     * @param string $addWhereCondition
     * @return array
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function getTreeData(
        $rootNodeID = null, $maxLevels = null, $includeRootNode = true, $returnLeafData = false,
        $inversedBranchMode = false, $addWhereCondition = ""
    ) {
        $rootNodeTemplate = "SELECT -- FW_TreeModel::getTreeData
                @Lvl := $this->tableLevelColName,
                @Lft := $this->tableLeftColName,
                @Rgt := $this->tableRightColName
            FROM $this->tableName
            WHERE %WhereCondition%
            LIMIT 1
        ";
        $extraAttrsString = '';
        if ($this->extraTreeDataAttrs) {
            $extraAttrsString = ',' . implode(', ', $this->extraTreeDataAttrs);
        }
        $leafQuery = "
            ,$this->tableLeftColName AS NodeLft
            ,$this->tableRightColName AS NodeRgt
            ,NOT EXISTS(
                SELECT $this->tablePkName
                FROM $this->tableName
                WHERE
                    $this->tableLevelColName = NodeLevel + 1 AND
                    $this->tableLeftColName > NodeLft AND
                    $this->tableRightColName < NodeRgt
                ) AS isLeaf
        ";
        if (!$returnLeafData) {
            $leafQuery = "";
        }
        $treeQueryTemplate = "SELECT
                $this->tablePkName AS NodeID,
                $this->tableLevelColName AS NodeLevel,
                $this->tableTitleColName AS NodeTitle
                $leafQuery
                $extraAttrsString
            FROM $this->tableName
            WHERE
                $this->tableLeftColName %OperandLft% @Lft
                AND
                $this->tableRightColName %OperandRgt% @Rgt
                AND
                $this->tableLevelColName <= @Lvl + COALESCE(%MaxLevels%, 99)
                $addWhereCondition
            ORDER BY $this->tableLeftColName ASC
        ";
        if ($rootNodeID === null) {
            $rootNodeCondition = "$this->tableParentColName IS NULL";
        } else {
            $nodeID = intval($rootNodeID);
            $rootNodeCondition = "$this->tablePkName = $nodeID";
        }
        $selectRootNodeQuery = str_replace('%WhereCondition%', $rootNodeCondition, $rootNodeTemplate);
        FW_DB::query($selectRootNodeQuery);
        if ($includeRootNode) {
            $operandLft = '>=';
            $operandRgt = '<=';
        } else {
            $operandLft = '>';
            $operandRgt = '<';
        }
        if ($inversedBranchMode) {
            $operandLft = '<=';
            $operandRgt = '>=';
        }
        $selectTreeQuery = str_replace(
            array(
                '%OperandLft%',
                '%OperandRgt%',
                '%MaxLevels%',
            ),
            array(
                $operandLft,
                $operandRgt,
                $maxLevels === null ? 'NULL' : intval($maxLevels),
            ),
            $treeQueryTemplate
        );
        return FW_DB::getAll($selectTreeQuery);
    }

    /**
     * Adds total root node for tree
     *
     * @param array $attrs
     * @return int
     */
    public function addRootNode($attrs = array()) {
        if (!isset($attrs[$this->tablePkName])) {
            $attrs[$this->tablePkName] = FW_DB::getNextID($this->tableName);
        }
        $newNodeID = $attrs[$this->tablePkName];
        $attrBindString = FW_Sql::getAttrsBindString($attrs);
        $query = "INSERT INTO $this->tableName
            SET
                $this->tableParentColName = NULL
                ,$this->tableLeftColName = 1
                ,$this->tableRightColName = 2
                ,$this->tableLevelColName = 0
                $attrBindString
        ";
        FW_DB::query($query);
        return $newNodeID;
    }

    /**
     * Adds node as the first child for supplied parents node id
     *
     * - parent node (supplied node id)
     *     - [*NEW CHILD*] <- adds new child here
     *     - child 1
     *     - child 2
     *       ...
     *     - child n
     *
     * @param int $parentNodeID
     * @param array $attrs
     * @return int
     */
    public function addNodeAsFirstChildByParentNodeID($parentNodeID, array $attrs = array()) {
        FW_DB::startTransaction();
        $getControlAttrsQuery = "SELECT $this->tableLeftColName AS Lft, $this->tableLevelColName AS Level
            FROM $this->tableName
            WHERE $this->tablePkName = $parentNodeID";
        $obj = FW_DB::getRow($getControlAttrsQuery);
        $Lft = $obj->Lft;
        $Level = $obj->Level;
        $updateAffected = "UPDATE $this->tableName
            SET $this->tableLeftColName
                = IF($this->tableLeftColName > $Lft, $this->tableLeftColName + 2, $this->tableLeftColName),
                $this->tableRightColName
                = IF( $this->tableRightColName > $Lft, $this->tableRightColName + 2, $this->tableRightColName)
            WHERE $this->tableRightColName > $Lft
            ORDER BY $this->tableRightColName DESC";
        FW_DB::query($updateAffected);
        if (!isset($attrs[$this->tablePkName])) {
            $attrs[$this->tablePkName] = FW_DB::getNextID($this->tableName);
        }
        $newNodeID = $attrs[$this->tablePkName];
        $attrBindString = FW_Sql::getAttrsBindString($attrs);
        $insertNewNodeQuery = "INSERT INTO $this->tableName
            SET
                $this->tableParentColName = $parentNodeID
                ,$this->tableLeftColName = $Lft + 1
                ,$this->tableRightColName = $Lft + 2
                ,$this->tableLevelColName = $Level + 1
                $attrBindString
        ";
        FW_DB::query($insertNewNodeQuery);
        FW_DB::commit();
        return $newNodeID;
    }

    /**
     * Adds node as last child for supplied parent node id
     *
     * - parent node (supplied node id)
     *     - child 1
     *     - child 2
     *       ...
     *     - child n
     *     - [*NEW CHILD*] <- adds new child here
     *
     * @param int $parentNodeID
     * @param array $attrs
     * @return int
     */
    public function addNodeAsLastChildByParentNodeID($parentNodeID, $attrs = array()) {
        FW_DB::startTransaction();
        $getControlAttrsQuery = "SELECT $this->tableRightColName AS Rgt, $this->tableLevelColName AS Level
            FROM $this->tableName
            WHERE $this->tablePkName = $parentNodeID";
        $obj = FW_DB::getRow($getControlAttrsQuery);
        $Rgt = $obj->Rgt;
        $Level = $obj->Level;
        $updateAffected = "UPDATE $this->tableName
            SET $this->tableLeftColName
                = IF($this->tableLeftColName >= $Rgt, $this->tableLeftColName + 2, $this->tableLeftColName),
                $this->tableRightColName
                = IF($this->tableRightColName >= $Rgt, $this->tableRightColName + 2, $this->tableRightColName)
            WHERE $this->tableRightColName >= $Rgt
            ORDER BY $this->tableRightColName DESC";
        FW_DB::query($updateAffected);
        if (!isset($attrs[$this->tablePkName])) {
            $attrs[$this->tablePkName] = FW_DB::getNextID($this->tableName);
        }
        $newNodeID = $attrs[$this->tablePkName];
        $attrBindString = FW_Sql::getAttrsBindString($attrs);
        $insertNewNodeQuery = "INSERT INTO $this->tableName
            SET
                $this->tableParentColName = $parentNodeID
                ,$this->tableLeftColName = $Rgt
                ,$this->tableRightColName = $Rgt + 1
                ,$this->tableLevelColName = $Level + 1
                $attrBindString
        ";
        FW_DB::query($insertNewNodeQuery);
        FW_DB::commit();
        return $newNodeID;
    }

    /**
     * Adds node as sibling before supplied node id
     *
     * - parent node
     *     - child node 1
     *     - [*NEW CHILD*] <- adds new child here
     *     - child node 2 (supplied node id)
     *      ...
     *     - child node n
     *
     * @param int $siblingNodeID
     * @param array $attrs
     * @return int
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function addNodeAsSiblingBeforeNodeID($siblingNodeID, $attrs = array()) {
        FW_DB::startTransaction();
        $getControlAttrsQuery = "SELECT
                 $this->tableLeftColName AS Lft
                ,$this->tableParentColName AS ParentNodeID
                ,$this->tableLevelColName AS Level
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $siblingNodeID
        ";
        $obj = FW_DB::getRow($getControlAttrsQuery);
        $Lft = $obj->Lft;
        $ParentNodeID = $obj->ParentNodeID;
        $Level = $obj->Level;
        $updateAffected = "UPDATE $this->tableName
            SET $this->tableLeftColName
                = IF($this->tableLeftColName >= $Lft, $this->tableLeftColName + 2, $this->tableLeftColName),
                $this->tableRightColName
                = IF($this->tableRightColName > $Lft, $this->tableRightColName + 2, $this->tableRightColName)
            WHERE $this->tableRightColName > $Lft";
        FW_DB::query($updateAffected);
        if (!isset($attrs[$this->tablePkName])) {
            $attrs[$this->tablePkName] = FW_DB::getNextID($this->tableName);
        }
        $newNodeID = $attrs[$this->tablePkName];
        $attrBindString = FW_Sql::getAttrsBindString($attrs);
        $insertNewNodeQuery = "INSERT INTO $this->tableName
            SET
                $this->tableParentColName = $ParentNodeID
                ,$this->tableLeftColName = $Lft
                ,$this->tableRightColName = $Lft + 1
                ,$this->tableLevelColName = $Level
                $attrBindString
        ";
        FW_DB::query($insertNewNodeQuery);
        FW_DB::commit();
        return $newNodeID;
    }

    /**
     * Adds node as sibling after supplied node id
     *
     * - parent node
     *     - child node 1
     *     - child node 2 (supplied node id)
     *     - [*NEW CHILD*] <- adds new child here
     *      ...
     *     - child node n
     *
     * @param int $siblingNodeID
     * @param array $attrs
     * @return int
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function addNodeAsSiblingAfterNodeID($siblingNodeID, $attrs = array()) {
        FW_DB::startTransaction();
        $getControlAttrsQuery = "SELECT
                $this->tableRightColName AS Rgt
                ,$this->tableParentColName AS ParentNodeID
                ,$this->tableLevelColName AS Level
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $siblingNodeID
        ";
        $obj = FW_DB::getRow($getControlAttrsQuery);
        $Rgt = $obj->Rgt;
        $ParentNodeID = $obj->ParentNodeID;
        $Level = $obj->Level;
        $updateAffected = "UPDATE $this->tableName
            SET $this->tableLeftColName
                = IF($this->tableLeftColName > $Rgt, $this->tableLeftColName + 2, $this->tableLeftColName),
                $this->tableRightColName
                = IF($this->tableRightColName > $Rgt, $this->tableRightColName + 2, $this->tableRightColName)
            WHERE
                $this->tableRightColName > $Rgt
        ";
        FW_DB::query($updateAffected);
        if (!isset($attrs[$this->tablePkName])) {
            $attrs[$this->tablePkName] = FW_DB::getNextID($this->tableName);
        }
        $newNodeID = $attrs[$this->tablePkName];
        $attrBindString = FW_Sql::getAttrsBindString($attrs);
        $insertNewNodeQuery = "INSERT INTO $this->tableName
            SET
                $this->tableParentColName = $ParentNodeID
                ,$this->tableLeftColName = $Rgt + 1
                ,$this->tableRightColName = $Rgt + 2
                ,$this->tableLevelColName = $Level
                $attrBindString
        ";
        FW_DB::query($insertNewNodeQuery);
        FW_DB::commit();
        return $newNodeID;
    }

    /**
     * Removes supplied node and all children is any exists (recursive deletion)
     *
     * - parent node
     *     - child node 1
     *     - child node 2 (supplied node id) [*DELETED*]
     *         - child node 2.1 [*DELETED*]
     *             - child node 2.1.1 [*DELETED*]
     *         - child node 2.2 [*DELETED*]
     *      ...
     *     - child node n
     *
     * @param int $nodeID
     * @return int
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function removeNodeByNodeID($nodeID) {
        $getControlAttrsQuery = "
            SELECT
                 $this->tableLeftColName AS Lft
                ,$this->tableRightColName AS Rgt
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $nodeID
        ";
        $obj = FW_DB::getRow($getControlAttrsQuery);
        if (isset($obj)) {
            FW_DB::startTransaction();
            $Lft = $obj->Lft;
            $Rgt = $obj->Rgt;
            $deleteNodeQuery = "
                DELETE FROM
                    $this->tableName
                WHERE
                    $this->tableRightColName <= $Rgt
                    AND
                    $this->tableLeftColName >= $Lft
                ORDER BY
                    $this->tableLeftColName DESC
            ";
            FW_DB::query($deleteNodeQuery);
            $updateAffected = "UPDATE $this->tableName
                SET $this->tableLeftColName = IF(
                    $this->tableLeftColName > $Rgt,  $this->tableLeftColName - 1 - $Rgt + $Lft, $this->tableLeftColName
                ),
                $this->tableRightColName = IF(
                    $this->tableRightColName >= $Rgt,
                    $this->tableRightColName - 1 - $Rgt + $Lft,
                    $this->tableRightColName
                )
                WHERE $this->tableRightColName >= $Rgt";
            FW_DB::query($updateAffected);
            FW_DB::commit();
        }
        return $nodeID;
    }

    public function hasPrevSibling($nodeID) {
        $prevSiblNodeID = $this->getPrevSiblingNodeID($nodeID);
        return $prevSiblNodeID ? true : false;
    }

    public function hasNextSibling($nodeID) {
        $nextSiblNodeID = $this->getNextSiblingNodeID($nodeID);
        return $nextSiblNodeID ? true : false;
    }

    /**
     * @param int $nodeID
     * @return bool
     * @throws FW_Exception
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function moveNodeOneStepBackward($nodeID) {
        if ($this->hasPrevSibling($nodeID)) {
            try {
                FW_DB::startTransaction();
                $A_NodeID = $nodeID;
                $query = "
                    SELECT
                        p.$this->tablePkName AS A_NodeID,
                        p.$this->tableLeftColName AS A_NodeLft,
                        p.$this->tableRightColName AS A_NodeRgt,
                        p.$this->tableRightColName - p.$this->tableLeftColName + 1 AS A_Distance,
                        psb.$this->tableLeftColName AS B_NodeLft,
                        psb.$this->tableRightColName AS B_NodeRgt,
                        psb.$this->tableRightColName - psb.$this->tableLeftColName + 1 AS B_Distance
                    FROM
                        $this->tableName p
                    INNER JOIN
                        $this->tableName psb
                        ON
                        psb.$this->tableRightColName = p.$this->tableLeftColName - 1
                    WHERE
                        p.$this->tablePkName = $A_NodeID
                ";
                $obj = FW_DB::getRow($query);
                $A_NodeLft = $obj->A_NodeLft;
                $A_NodeRgt = $obj->A_NodeRgt;
                $A_Distance = $obj->A_Distance;
                $B_NodeLft = $obj->B_NodeLft;
                $B_NodeRgt = $obj->B_NodeRgt;
                $B_Distance = $obj->B_Distance;
                $query = "
                    UPDATE
                        $this->tableName
                    SET
                        $this->tableFlagColName = 1
                    WHERE
                        $this->tableLeftColName >= $B_NodeLft
                        AND
                        $this->tableRightColName <= $B_NodeRgt
                ";
                FW_DB::query($query);
                $query = "
                    UPDATE
                        $this->tableName
                    SET
                        $this->tableLeftColName = $this->tableLeftColName - $B_Distance,
                        $this->tableRightColName = $this->tableRightColName - $B_Distance
                    WHERE
                        $this->tableLeftColName >= $A_NodeLft
                        AND
                        $this->tableRightColName <= $A_NodeRgt
                ";
                FW_DB::query($query);
                $query = "
                    UPDATE
                        $this->tableName
                    SET
                        $this->tableLeftColName = $this->tableLeftColName + $A_Distance,
                        $this->tableRightColName = $this->tableRightColName + $A_Distance,
                        $this->tableFlagColName = 0
                    WHERE
                        $this->tableLeftColName >= $B_NodeLft
                        AND
                        $this->tableRightColName <= $B_NodeRgt
                        AND
                        $this->tableFlagColName = 1
                ";
                FW_DB::query($query);
                FW_DB::commit();
            } catch (Exception $e) {
                FW_DB::rollback();
                throw new FW_Exception(tra('MSG.MovingNodeFailed'));
            }
        } else {
            throw new FW_Exception(tra('MSG.NodeDoesNotHaveProperSibling'));
        }
        return true;
    }

    public function moveNodeOneStepForward($nodeID) {
        if ($this->hasNextSibling($nodeID)) {
            try {
                $nextSiblNodeID = $this->getNextSiblingNodeID($nodeID);
                $this->moveNodeOneStepBackward($nextSiblNodeID);
            } catch (Exception $e) {
                throw new FW_Exception(tra('MSG.MovingNodeFailed'));
            }
        } else {
            throw new FW_Exception(tra('MSG.NodeDoesNotHaveProperSibling'));
        }
        return true;
    }

    /**
     * Update node by node id
     *
     *
     * @param int $nodeID
     * @param array $attrs
     * @return int
     */
    public function updateNodeByNodeID($nodeID, $attrs = array()) {
        if (count($attrs) > 0) {
            $attrsBindString = FW_Sql::getAttrsBindString($attrs, '');
            $updateNodeDataQuery = "UPDATE " . $this->tableName . " SET $attrsBindString
                WHERE $this->tablePkName = $nodeID";
            FW_DB::query($updateNodeDataQuery);
        }
        return $nodeID;
    }

    public function isNodeIDExist($nodeID) {
        $nodeQuery = "SELECT COUNT(*) AS Num
            FROM " . $this->tableName . "
            WHERE $this->tablePkName = $nodeID";
        return FW_DB::getOne($nodeQuery);
    }

    /**
     * Moves supplied node and all children under the supplied parent node as its last child
     *
     * @param int $nodeID
     * @param int $parentNodeID
     * @param array $attrs
     * @return int
     * @throws Exception
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function moveNodeAsLastChildByParentNodeID($nodeID, $parentNodeID, array $attrs = array()) {
        if ($nodeID == $parentNodeID) {
            return $nodeID;
        }
        try {
            FW_DB::startTransaction();
            $getNodeQuery = "SELECT
                     $this->tableLeftColName AS moveLft
                    ,$this->tableRightColName AS moveRgt
                    ,$this->tableRightColName - $this->tableLeftColName + 1 AS moveDistance
                    ,$this->tableLevelColName AS moveLevel
                FROM " . $this->tableName . "
                WHERE " . $this->tablePkName . " = $nodeID";
            $obj = FW_DB::getRow($getNodeQuery);
            $moveLft = $obj->moveLft;
            $moveRgt = $obj->moveRgt;
            $moveDistance = $obj->moveDistance;
            $moveLevel = $obj->moveLevel;
            /**
            *    select parent node
            */
            $getParentNodeQuery = "
                SELECT
                    $this->tableRightColName AS parentRgt
                    ,(Lft BETWEEN $moveLft AND $moveRgt) AS STATUS
                    ,$this->tableLevelColName AS parentLevel
                FROM
                    " . $this->tableName . "
                WHERE
                    " . $this->tablePkName . " = $parentNodeID
            ";
            $_result = FW_DB::getRow($getParentNodeQuery);
            $parentRgt = $_result->parentRgt;
            $parentLevel = $_result->parentLevel;
            if ((int)$_result->STATUS == 1) {
                throw new FW_Exception('The parent is a child of the current node, unable to move.');
            }
            /**
            *    set new distance in parents
            */
            $setDistanceQuery = "UPDATE " . $this->tableName . "
                SET $this->tableLeftColName
                    = IF(
                        $this->tableLeftColName > $parentRgt,
                        $this->tableLeftColName + $moveDistance,
                        $this->tableLeftColName
                    ),
                    $this->tableRightColName
                    = IF(
                        $this->tableRightColName >= $parentRgt,
                        $this->tableRightColName + $moveDistance,
                        $this->tableRightColName
                    )
                WHERE $this->tableRightColName >= $parentRgt";
            FW_DB::query($setDistanceQuery);
            /**
            *    select the node to move again
            */
            $_SQL = "
                SELECT
                     $this->tableLeftColName AS moveLft
                    ,$this->tableRightColName AS moveRgt
                    ,IF(
                        $parentRgt >= $this->tableLeftColName,
                        $parentRgt - $this->tableLeftColName,
                        $this->tableLeftColName - $parentRgt
                    ) AS moveNewDistance
                    ,IF( $parentRgt >= $this->tableLeftColName, 1,  0 ) AS moveNewDistanceOperator
                FROM
                    " . $this->tableName . "
                WHERE
                    " . $this->tablePkName . " = $nodeID
            ";
            $obj = FW_DB::getRow($_SQL);
            $moveLft = $obj->moveLft;
            $moveRgt = $obj->moveRgt;
            $moveNewDistance = $obj->moveNewDistance;
            $moveNewDistanceOper = $obj->moveNewDistanceOperator;
            /**
            *    move the node
            */
            $moveNodeQuery = "
                UPDATE
                    " . $this->tableName . "
                SET
                     $this->tableLeftColName =
                        IF(
                            $moveNewDistanceOper = 1,
                            $this->tableLeftColName + $moveNewDistance,
                            $this->tableLeftColName - $moveNewDistance
                        )
                    ,$this->tableRightColName
                        = IF(
                            $moveNewDistanceOper = 1,
                            $this->tableRightColName + $moveNewDistance,
                            $this->tableRightColName - $moveNewDistance
                        )
                    ,$this->tableParentColName
                        = IF( " . $this->tablePkName . " = $nodeID , $parentNodeID , $this->tableParentColName )
                    ,$this->tableLevelColName = $this->tableLevelColName - $moveLevel + 1 + $parentLevel
                WHERE
                    $this->tableRightColName <= $moveRgt
                    AND
                    $this->tableLeftColName >= $moveLft
            ";
            FW_DB::query($moveNodeQuery);
            /**
            *    update distances
            */
            $updateDistanceQuery = "
                UPDATE
                    " . $this->tableName . "
                SET
                     $this->tableLeftColName
                        = IF(
                            $this->tableLeftColName > $moveRgt,
                            $this->tableLeftColName - $moveDistance,
                            $this->tableLeftColName
                        )
                    ,$this->tableRightColName
                        = IF(
                            $this->tableRightColName >= $moveRgt,
                            $this->tableRightColName - $moveDistance,
                            $this->tableRightColName
                        )
                WHERE
                    $this->tableRightColName >= $moveRgt
            ";
            FW_DB::query($updateDistanceQuery);
            /**
             *     update node data
             */
            if (count($attrs) > 0) {
                $attrsBindString = FW_Sql::getAttrsBindString($attrs, '');
                $updateNodeDataQuery = "UPDATE " . $this->tableName . "
                    SET
                        $attrsBindString
                    WHERE
                        $this->tablePkName = $nodeID
                ";
                FW_DB::query($updateNodeDataQuery);
            }
            FW_DB::commit();
            return $nodeID;
        } catch (Exception $e) {
            FW_DB::rollback();
            $errorCode = $e->getCode();
            $errorText = $e->getMessage();
            throw new Exception($errorText, $errorCode);
        }
    }

    /**
     * Moves supplied node and all children before the supplied node id
     *
     * @param int $nodeID
     * @param int $referenceNodeID
     * @param array $attrs
     * @param bool $transaction
     * @return int
     * @throws Exception
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    public function moveNodeBeforeNodeID($nodeID, $referenceNodeID, array $attrs = array(), $transaction = true) {
        if ($nodeID == $referenceNodeID) {
            return $nodeID;
        }
        try {
            /**
            *    select the node to move
            */
            if ($transaction) {
                FW_DB::startTransaction();
            }
            $getNodeQuery = "
                SELECT
                     $this->tableLeftColName AS NodeLft
                    ,$this->tableRightColName AS NodeRgt
                    ,$this->tableRightColName - $this->tableLeftColName + 1 AS NodeDist
                    ,$this->tableLevelColName AS NodeLevel
                FROM
                    " . $this->tableName . "
                WHERE
                    " . $this->tablePkName . " = $nodeID

            ";
            $obj = FW_DB::getRow($getNodeQuery);
            $NodeLft = $obj->NodeLft;
            $NodeRgt = $obj->NodeRgt;
            $NodeDist = $obj->NodeDist;
            $NodeLevel = $obj->NodeLevel;
            /**
            *    select reference node
            */
            $getReferenceNode = "
                SELECT
                     $this->tableLeftColName AS RefNodeLft
                    ,$this->tableLevelColName AS RefNodeLevel
                    ,$this->tableParentColName AS RefNodeParentID
                    ,(Lft BETWEEN $NodeLft AND $NodeRgt) AS IsChild
                    ,IF($NodeLft < $this->tableLeftColName, $NodeLft, $NodeLft + $NodeDist) AS MovedNodeLft
                FROM
                    " . $this->tableName . "
                WHERE
                    " . $this->tablePkName . " = $referenceNodeID

            ";
            $_result = FW_DB::getRow($getReferenceNode);
            $RefNodeLft = $_result->RefNodeLft;
            $RefNodeLevel = $_result->RefNodeLevel;
            $RefNodeParentID = $_result->RefNodeParentID;
            $MovedNodeLft = $_result->MovedNodeLft;
            if ((int)$_result->IsChild == 1) {
                throw new FW_Exception('The reference node is a child of the current node, unable to move.');
            }
            /**
             * make place for the new node by shifting everything after the
             * reference node, including the ref node itself
             */
            $setDistanceQuery = "
                UPDATE
                    " . $this->tableName . "
                SET
                     $this->tableLeftColName
                        = IF(
                            $this->tableLeftColName >= $RefNodeLft,
                            $this->tableLeftColName + $NodeDist,
                            $this->tableLeftColName
                        )
                    ,$this->tableRightColName
                        = IF(
                            $this->tableRightColName >= $RefNodeLft,
                            $this->tableRightColName + $NodeDist,
                            $this->tableRightColName
                        )
                WHERE
                    $this->tableRightColName >= $RefNodeLft
            ";
            FW_DB::query($setDistanceQuery);
            /**
            *    update the node's (+kids') coordinates according to distance
            */
            $moveNodeQuery = "
                UPDATE
                    " . $this->tableName . "
                SET
                     $this->tableLeftColName = $this->tableLeftColName + $RefNodeLft - $MovedNodeLft
                    ,$this->tableRightColName = $this->tableRightColName + $RefNodeLft - $MovedNodeLft
                    ,$this->tableParentColName =
                        IF( " . $this->tablePkName . " = $nodeID , $RefNodeParentID, $this->tableParentColName)
                    ,$this->tableLevelColName =  $this->tableLevelColName - $NodeLevel + $RefNodeLevel
                WHERE
                    $this->tableLeftColName >= $MovedNodeLft
                    AND
                    $this->tableRightColName <= $MovedNodeLft + $NodeDist - 1
            ";
            FW_DB::query($moveNodeQuery);
            /**
             *    cleaning up the distances after the move
             */
            $updateDistanceQuery = "
                UPDATE
                    " . $this->tableName . "
                SET
                     $this->tableLeftColName =
                        IF(
                            $this->tableLeftColName >= $MovedNodeLft,
                            $this->tableLeftColName - $NodeDist,
                            $this->tableLeftColName
                        )
                    ,$this->tableRightColName
                        = IF(
                            $this->tableRightColName > $MovedNodeLft,
                            $this->tableRightColName - $NodeDist,
                            $this->tableRightColName
                        )
                WHERE
                $this->tableRightColName > $MovedNodeLft;
            ";
            FW_DB::query($updateDistanceQuery);
            /**
             *     update node data
             */
            if (count($attrs) > 0) {
                $attrsBindString = FW_Sql::getAttrsBindString($attrs, '');
                $updateNodeDataQuery = "
                    UPDATE
                        " . $this->tableName . "
                    SET
                        $attrsBindString
                    WHERE
                        $this->tablePkName = $nodeID
                ";
                FW_DB::query($updateNodeDataQuery);
            }
            if ($transaction) {
                FW_DB::commit();
            }
            return $nodeID;
        } catch (Exception $e) {
            if ($transaction) {
                FW_DB::rollback();
            }
            dump($e->getMessage());
            $errorCode = $e->getCode();
            $errorText = $e->getMessage();
            throw new Exception($errorText, $errorCode);
        }
    }

    /**
     * Finds out if supplied ancestor node is really ancestor of supplied descendant node
     *
     * - parent node
     *     - child node 1
     *     - child node 2 (supplied ancestor node id)
     *         - child node 2.1 (supplied descendant node id) [*TRUE*]
     *             - child node 2.1.1
     *         - child node 2.2
     *      ...
     *     - child node n (supplied descendant node id) [*FALSE*]
     *
     * @param int $ancestorNodeID
     * @param int $descendantNodeID
     * @return bool
     */
    public function isAncestor($ancestorNodeID, $descendantNodeID) {
        $query = "
            SELECT
                IF(
                    a.$this->tableLeftColName < d.$this->tableLeftColName
                    AND
                    a.$this->tableRightColName > d.$this->tableRightColName,
                    1,
                    0
                ) AS IsAncestor
            FROM
                $this->tableName AS a
            INNER JOIN
                $this->tableName AS d
                ON
                d.$this->tablePkName = $descendantNodeID
            WHERE
                a.$this->tablePkName = $ancestorNodeID;
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    /**
     * Finds out if supplied ancestor node is really ancestor of supplied descendant node
     *
     * - parent node
     *     - child node 1
     *     - child node 2 (supplied ancestor node id)
     *         - child node 2.1 (supplied descendant node id) [*TRUE*]
     *             - child node 2.1.1
     *         - child node 2.2
     *      ...
     *     - child node n (supplied descendant node id) [*FALSE*]
     *
     * @param int $ancestorNodeID
     * @param int $descendantNodeID
     * @return bool
     */
    public function isDescendant($descendantNodeID, $ancestorNodeID) {
        $query = "
            SELECT
                IF(
                    d.$this->tableLeftColName > a.$this->tableLeftColName
                    AND
                    d.$this->tableRightColName < a.$this->tableRightColName,
                    1,
                    0
                ) AS IsDescendant
            FROM
                $this->tableName AS d
            INNER JOIN
                $this->tableName AS a
                ON
                a.$this->tablePkName = $ancestorNodeID
            WHERE
                d.$this->tablePkName = $descendantNodeID;
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    /**
     * Finds out if supplied parent node is really parent (means direct ancestor) of supplied child node
     *
     * - parent node (supplied parent node id)
     *     - child node 1 (supplied child node id) [*TRUE*]
     *     - child node 2
     *         - child node 2.1 (supplied child node id) [*FALSE*] - supplied parent is not direct ancestor
     *             - child node 2.1.1
     *         - child node 2.2
     *      ...
     *     - child node n (supplied child node id) [*TRUE*]
     *
     * @param int $parentNodeID
     * @param int $childNodeID
     * @return bool
     */
    public function isParent($parentNodeID, $childNodeID) {
        $query = "
            SELECT
                COUNT($this->tablePkName) AS IsParent
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $childNodeID
                AND
                $this->tableParentColName = $parentNodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    /**
     * Finds out if supplied child node is really child (means direct descendant) of supplied parent node
     *
     * - parent node (supplied parent node id)
     *     - child node 1 (supplied child node id) [*TRUE*]
     *     - child node 2
     *         - child node 2.1 (supplied child node id) [*FALSE*] - supplied child is not direct descendant
     *             - child node 2.1.1
     *         - child node 2.2
     *      ...
     *     - child node n (supplied child node id) [*TRUE*]
     *
     * @param int $childNodeID
     * @param int $parentNodeID
     * @return bool
     */
    public function isChild($childNodeID, $parentNodeID) {
        $query = "
            SELECT
                COUNT($this->tablePkName) AS IsChild
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $childNodeID
                AND
                $this->tableParentColName = $parentNodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    public function isFirstChild($childNodeID, $parentNodeID = null) {
        if ($parentNodeID == null) {
            $parentNodeID = $this->getParentNodeID($childNodeID);
        }
        $query = "
            SELECT
                (pc.$this->tableLeftColName = pp.$this->tableLeftColName + 1) AS IsFirstChild
            FROM
                $this->tableName pc
            INNER JOIN
                $this->tableName pp
                ON
                pp.$this->tablePkName = $parentNodeID
            WHERE
                pc.$this->tablePkName = $childNodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    public function isLastChild($childNodeID, $parentNodeID = null) {
        if ($parentNodeID == null) {
            $parentNodeID = $this->getParentNodeID($childNodeID);
        }
        $query = "
            SELECT
                (pp.$this->tableRightColName = pc.$this->tableRightColName + 1) AS IsLastChild
            FROM
                $this->tableName pc
            INNER JOIN
                $this->tableName pp
                ON
                pp.$this->tablePkName = $parentNodeID
            WHERE
                pc.$this->tablePkName = $childNodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    public function isOnlyChild($childNodeID, $parentNodeID = null) {
        if ($parentNodeID == null) {
            $parentNodeID = $this->getParentNodeID($childNodeID);
        }
        $query = "
            SELECT
                (pp.$this->tableRightColName = pc.$this->tableRightColName + 1
                 AND
                 pc.$this->tableLeftColName = pp.$this->tableLeftColName + 1
                ) AS IsOnlyChild
            FROM
                $this->tableName pc
            INNER JOIN
                $this->tableName pp
                ON
                pp.$this->tablePkName = $parentNodeID
            WHERE
                pc.$this->tablePkName = $childNodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    /**
     * Finds out if supplied node has any children
     *
     * @param int $nodeID
     * @return int
     */
    public function hasChildren($nodeID) {
        $query = "
            SELECT
                $this->tableLeftColName + 1 < $this->tableRightColName AS HasChildren
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $nodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    /**
     * Finds out if supplied node is leaf (means has no children)
     *
     * @param int $nodeID
     * @return int
     */
    public function isLeaf($nodeID) {
        $query = "
            SELECT
                $this->tableLeftColName + 1 = $this->tableRightColName AS IsLeaf
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $nodeID
        ";
        return FW_DB::getOne($query) ? true : false;
    }

    /**
     * Gets the number of all node descendants (not just children)
     *
     * @param int $nodeID
     * @return int
     */
    public function getDescendantCount($nodeID) {
        $query = "
            SELECT
                CAST(
                    ($this->tableRightColName - $this->tableLeftColName - 1) / 2 AS UNSIGNED
                ) AS DescendantCount
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $nodeID
        ";
        return FW_DB::getOne($query);
    }

    /**
     * Gets the number of children (just direct descendants) for supplied node
     *
     * @param int $nodeID
     * @return int
     */
    public function getChildrenCount($nodeID) {
        $query = "
            SELECT
                COUNT($this->tablePkName) AS ChildrenCount
            FROM
                $this->tableName
            WHERE
                $this->tableParentColName = $nodeID
        ";
        return FW_DB::getOne($query);
    }

    /**
     * Gets the depth level for supplied node
     *
     * @param int $nodeID
     * @return int
     */
    public function getLevel($nodeID) {
        $query = "
            SELECT
                $this->tableLevelColName AS Level
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $nodeID
        ";
        return FW_DB::getOne($query);
    }

    public function getPrevSiblingNodeID($nodeID) {
        $query = "
            SELECT
                psb.$this->tablePkName
            FROM
                $this->tableName p
            INNER JOIN
                $this->tableName psb
                ON
                psb.$this->tableRightColName = p.$this->tableLeftColName - 1
            WHERE
                p.$this->tablePkName = $nodeID
        ";
        return FW_DB::getOne($query);
    }

    public function getNextSiblingNodeID($nodeID) {
        $query = "
            SELECT
                psa.$this->tablePkName
            FROM
                $this->tableName p
            INNER JOIN
                $this->tableName psa
                ON
                psa.$this->tableLeftColName = p.$this->tableRightColName + 1
            WHERE
                p.$this->tablePkName = $nodeID
        ";
        return FW_DB::getOne($query);
    }

    /**
     * Gets the first not empty value (means first not null) from supplied node attribute by path from descendant
     * to root node.
     * This mechanism is treated like inheritance in tree structure.
     *
     * Example: we would like to get first filled value of attribute PageSectionSetID by path from supplied node
     * to root node
     *
     * - root node
     *     - node 1 [PageSectionSet = 1]
     *         - node 1.1
     *         - node 2.2 [PageSectionSet = 2] <- [*finds this one, if this would be null, then it goes way up
     * to 'node 1'*]
     *             - node 2.2.1
     *             - node 2.2.2  [PageSectionSet = NULL]
     *                 - node 2.2.2.1 [PageSectionSet = NULL] (supplied node id)
     *     - node 2
     *
     * @param int $descendantNodeID
     * @param string $attrName
     * @return mixed
     */
    public function getInheritedValueByAttrName($descendantNodeID, $attrName) {
        $query = "
            SELECT
                $attrName AS IheritedAttrValue
            FROM (
                SELECT
                    p.$attrName
                FROM
                    $this->tableName c
                INNER JOIN
                    $this->tableName p
                    ON
                    p.$this->tableLeftColName <= c.$this->tableLeftColName
                    AND
                    p.$this->tableRightColName >= c.$this->tableRightColName
                WHERE
                    c.$this->tablePkName = $descendantNodeID
                ORDER BY
                    p.$this->tableRightColName
                ) AS iavp
            WHERE
                $attrName IS NOT NULL
            LIMIT
                1
        ";
        return FW_DB::getOne($query);
    }

    /**
     * Gets the node path as string from root to node (or inversed when $pathFromRootNode is false)
     * delimited by $pathSeparator
     * from $pathRootLevel (use this level to avoid displaying root nodes of zero or first level)
     *
     * @param int $nodeID
     * @param int $pathRootLevel
     * @param bool $pathFromRootNode
     * @param string $pathSeparator
     * @return string
     */
    public function getNodePathAsString($nodeID, $pathRootLevel = 2, $pathFromRootNode = true, $pathSeparator = ' � ') {
        $nodeID = intval($nodeID);
        $pathRootLevel = intval($pathRootLevel);
        $orderBy = $pathFromRootNode ? $this->tableLeftColName : $this->tableRightColName;
        $query = "
            SELECT
                GROUP_CONCAT(
                    p.$this->tableTitleColName
                    ORDER BY
                    p.$orderBy
                    SEPARATOR
                    '$pathSeparator'
                ) AS Path,
                1 AS GroupByOne
            FROM
                $this->tableName c
            INNER JOIN
                $this->tableName p
                ON
                p.$this->tableLeftColName <= c.$this->tableLeftColName
                AND
                p.$this->tableRightColName >= c.$this->tableRightColName
                AND
                p.$this->tableLevelColName > $pathRootLevel
            WHERE
                c.$this->tablePkName = $nodeID
            GROUP BY
                GroupByOne
            ;
        ";
        return FW_DB::getOne($query);
    }

    /**
     * Gets the node path as array from root to node (or inversed when $pathFromRootNode is false)
     * from $pathRootLevel (use this level to avoid displaying root nodes of zero or first level)
     *
     * @param int $nodeID
     * @param array $getAttrs
     * @param int $pathRootLevel
     * @param bool $pathFromRootNode
     * @return array
     */
    public function getNodePathAsArray($nodeID, $getAttrs = array(), $pathRootLevel = 2, $pathFromRootNode = true) {
        $nodeID = intval($nodeID);
        $pathRootLevel = intval($pathRootLevel);
        $additionalAttrs = FW_Sql::getAttrsBindString($getAttrs);
        $orderBy = $pathFromRootNode ? $this->tableLeftColName : $this->tableRightColName;
        $query = "
            SELECT
                p.PageTitle
                $additionalAttrs
            FROM
                $this->tableName c
            INNER JOIN
                $this->tableName p
                ON
                p.$this->tableLeftColName <= c.$this->tableLeftColName
                AND
                p.$this->tableRightColName >= c.$this->tableRightColName
                AND
                p.$this->tableLevelColName >= $pathRootLevel
            WHERE
                c.$this->tablePkName = $nodeID
            ORDER BY
                p.$orderBy
        ";
        return FW_DB::getAll($query);
    }

    /**
     * Gets the node's parent node ID
     *
     * @param int $nodeID
     * @return int
     */
    public function getParentNodeID($nodeID) {
        $nodeID = intval($nodeID);
        $query = "
            SELECT
                $this->tableParentColName AS ParentNodeID
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $nodeID
            LIMIT
                1
        ";
        return FW_DB::getOne($query);
    }

    /**
     * Gets the max tree depth
     *
     * @param int|null $fromNodeID
     * @return int
     */
    public function getTreeDepth($fromNodeID = null) {
        if ($fromNodeID == null) {
            $query = "
                SELECT
                    MAX($this->tableLevelColName) AS MaxLevel
                FROM
                    $this->tableName
            ";
        } else {
            $query = "
                SELECT
                    MAX(pa.$this->tableLevelColName) - ps.$this->tableLevelColName AS MaxLevel
                FROM
                    $this->tableName pa
                INNER JOIN
                    $this->tableName ps
                    ON
                    ps.$this->tablePkName = $fromNodeID
            ";
        }
        return intval(FW_DB::getOne($query));
    }

    public function refreshIndicesFromParentIDs() {
        $orderedNodesQuery = "
            SELECT
                $this->tablePkName AS NodeID,
                $this->tableParentColName AS ParentNodeID
            FROM
                $this->tableName
            WHERE
                $this->tableLevelColName > 1
            ORDER BY
                $this->tableParentColName, $this->tableLevelColName";
        $nullifyIndicesQuery = "
            UPDATE $this->tableName SET
                $this->tableLeftColName = NULL,
                $this->tableRightColName = NULL";
        $setStartingIndices = "
            UPDATE $this->tableName SET
                $this->tableLeftColName = 1,
                $this->tableRightColName = 2
            WHERE $this->tableLevelColName = 1";
        $orderedNodes = FW_DB::getAll($orderedNodesQuery);
        FW_DB::startTransaction();
            FW_DB::query($nullifyIndicesQuery);
            FW_DB::query($setStartingIndices);
        FW_DB::commit();
        foreach ($orderedNodes as $node) {
            try {
                $this->refreshSingleNode($node->NodeID, $node->ParentNodeID);
            } catch (Exception $ex) {
                print_r($ex);
                break;
            }
        }
    }

    /**
     * @param int $nodeID
     * @param int $parentNodeID
     * @SuppressWarnings(PHPMD.ExcessiveMethodLength)
     */
    private function refreshSingleNode($nodeID, $parentNodeID) {
        $parentIndicesQuery = "
            SELECT
                $this->tableLeftColName AS Lft,
                $this->tableRightColName AS Rgt,
                $this->tableLevelColName AS Level
            FROM
                $this->tableName
            WHERE
                $this->tablePkName = $parentNodeID";
        $parentIndices = FW_DB::getRow($parentIndicesQuery);
        /**
         * fix:
         * recursively goes up the tree till it finds a node with
         * existing indices
         */
        if (empty($parentIndices->Lft) || empty($parentIndices->Rgt)) {
            $parentOfParentID = FW_DB::getOne("
                    SELECT {$this->tableParentColName}
                    FROM $this->tableName
                    WHERE
                        {$this->tablePkName} = $parentNodeID
            ");
            $this->refreshSingleNode($parentNodeID, $parentOfParentID);
            $parentIndices = FW_DB::getRow($parentIndicesQuery);
        }
        $shiftNodesQuery = "
            UPDATE $this->tableName SET
                $this->tableLeftColName
                    = IF(
                        $this->tableLeftColName >= $parentIndices->Rgt,
                        $this->tableLeftColName + 2,
                        $this->tableLeftColName
                    ),
                $this->tableRightColName
                    = IF(
                        $this->tableRightColName >= $parentIndices->Rgt,
                        $this->tableRightColName + 2,
                        $this->tableRightColName
                    )
            WHERE
                $this->tableRightColName >= $parentIndices->Rgt
            ORDER BY
                $this->tableRightColName DESC";
        $updateNodeQuery = "
            UPDATE $this->tableName SET
                Lft = $parentIndices->Rgt,
                Rgt = $parentIndices->Rgt + 1,
                Level = $parentIndices->Level + 1
            WHERE $this->tablePkName = $nodeID
        ";
        FW_DB::startTransaction();
            FW_DB::query($shiftNodesQuery);
            FW_DB::query($updateNodeQuery);
        FW_DB::commit();
    }

}

how can i move the node behind the target node, examp : moveNodeAfterNodeID

Thank you for your efford. It really enlightened me.