Move node in nested set

I see, that this topic is quite old, but anyway it's still unanswered. I got here from Google, and found no direct answer to this question.

So, after a little research I found quite easy solution.

Everything, what we gonna need to move our node is: node left and right positions, new parent node right position. The node to the new position then can be moved in four easy steps:

1. Change positions of node and all it's sub nodes into negative values,which are equal to current ones by module.
2. Move all positions "up", which are more, that pos_right of current node.
3. Move all positions "down", which are more, that pos_right of new parent node.
4. Change positions of current node and all it's subnodes, so that it's now will be exactly "after" (or "down") of new parent node.

That's theory, now - this algorithm realization in MySQL (example using PHP):

-- step 0: Initialize parameters.SELECT    @node_id := 1, --put there id of moving node     @node_pos_left := 0, --put there left position of moving node    @node_pos_right := 1, --put there right position of moving node    @parent_id := 2, --put there id of new parent node (there moving node should be moved)    @parent_pos_right := 4; --put there right position of new parent node (there moving node should be moved)SELECT    @node_size := @node_pos_right - @node_pos_left + 1; -- 'size' of moving node (including all it's sub nodes)-- step 1: temporary "remove" moving nodeUPDATE `list_items`SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)WHERE `pos_left` >= @node_pos_left AND `pos_right` <= @node_pos_right;-- step 2: decrease left and/or right position values of currently 'lower' items (and parents)UPDATE `list_items`SET `pos_left` = `pos_left` - @node_sizeWHERE `pos_left` > @node_pos_right;UPDATE `list_items`SET `pos_right` = `pos_right` - @node_sizeWHERE `pos_right` > @node_pos_right;-- step 3: increase left and/or right position values of future 'lower' items (and parents)UPDATE `list_items`SET `pos_left` = `pos_left` + @node_sizeWHERE `pos_left` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);UPDATE `list_items`SET `pos_right` = `pos_right` + @node_sizeWHERE `pos_right` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);-- step 4: move node (ant it's subnodes) and update it's parent item idUPDATE `list_items`SET    `pos_left` = 0-(`pos_left`)+IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size),    `pos_right` = 0-(`pos_right`)+IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size)WHERE `pos_left` <= 0-@node_pos_left AND `pos_right` >= 0-@node_pos_right;UPDATE `list_items`SET `parent_item_id` = @parent_idWHERE `item_id` = @node_id;

Please beware - there still may be some syntax errors in SQL code, because I actually use this algorithm in PHP like this:

$iItemId = 1;$iItemPosLeft = 0;$iItemPosRight = 1;$iParentId = 2;$iParentPosRight = 4;$iSize = $iPosRight - $iPosLeft + 1;$sql = array(    // step 1: temporary "remove" moving node    'UPDATE `list_items`    SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)    WHERE `pos_left` >= "'.$iItemPosLeft.'" AND `pos_right` <= "'.$iItemPosRight.'"',    // step 2: decrease left and/or right position values of currently 'lower' items (and parents)    'UPDATE `list_items`    SET `pos_left` = `pos_left` - '.$iSize.'    WHERE `pos_left` > "'.$iItemPosRight.'"',    'UPDATE `list_items`    SET `pos_right` = `pos_right` - '.$iSize.'    WHERE `pos_right` > "'.$iItemPosRight.'"',    // step 3: increase left and/or right position values of future 'lower' items (and parents)    'UPDATE `list_items`    SET `pos_left` = `pos_left` + '.$iSize.'    WHERE `pos_left` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',    'UPDATE `list_items`    SET `pos_right` = `pos_right` + '.$iSize.'    WHERE `pos_right` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',    // step 4: move node (ant it's subnodes) and update it's parent item id    'UPDATE `list_items`    SET        `pos_left` = 0-(`pos_left`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).',        `pos_right` = 0-(`pos_right`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).'    WHERE `pos_left` <= "'.(0-$iItemPosLeft).'" AND i.`pos_right` >= "'.(0-$iItemPosRight).'"',    'UPDATE `list_items`    SET `parent_item_id` = "'.$iParentItemId.'"    WHERE `item_id`="'.$iItemId.'"');foreach($sql as $sqlQuery){    mysql_query($sqlQuery);}

Please note also, that code may be optimized, but I going to leave it like that for better readability. Also consider table locking if you are using nested sets in multi-user systems.

Hope that my message will help to anyone, who will search for a solution after me. Any comments and corrections are also welcome.

Here is a solution that lets you move a node to any position in the tree, either as a sibling or a child with just a single input parameter - the new left position (newlpos) of the node.

Fundamentally there are three steps:

• Create new space for the subtree.
• Move the subtree into this space.
• Remove the old space vacated by the subtree.

In psuedo-sql, it looks like this:

// *  -- create new space for subtree *  UPDATE tags SET lpos = lpos + :width WHERE lpos >= :newlpos *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newlpos *  *  -- move subtree into new space *  UPDATE tags SET lpos = lpos + :distance, rpos = rpos + :distance *           WHERE lpos >= :tmppos AND rpos < :tmppos + :width *  *  -- remove old space vacated by subtree *  UPDATE tags SET lpos = lpos - :width WHERE lpos > :oldrpos *  UPDATE tags SET rpos = rpos - :width WHERE rpos > :oldrpos */

The :distance variable is the distance between the new and old positions, the :width is the size of the subtree, and :tmppos is used to keep track of the subtree being moved during the updates. These variables are defined as:

// calculate position adjustment variablesint width = node.getRpos() - node.getLpos() + 1;int distance = newlpos - node.getLpos();int tmppos = node.getLpos();        // backwards movement must account for new spaceif (distance < 0) {    distance -= width;    tmppos += width;}

For a complete code example, see my blog at

https://rogerkeays.com/how-to-move-a-node-in-nested-sets-with-sql

If you like this solution, please up-vote.

I know this is an old question, but I've just used the answer myself but for SQL Server. Should anyone want it, here is the code for a SQL Server Stored Proc based on the accepted answer.

CREATE PROCEDURE [dbo].[Item_Move]     @id uniqueidentifier,     @destinationId uniqueidentifierASBEGIN    SET NOCOUNT ON;    declare @moverLeft int,            @moverRight int,            @destinationRight int,            @node_size int    -- step 0: Initialize parameters.    SELECT         @moverLeft = leftExtent,         @moverRight = rightExtent     FROM         Item     WHERE         id = @id    SELECT         @destinationRight = rightExtent     FROM         Item     WHERE         id = @destinationId    SELECT        @node_size = @moverRight - @moverLeft + 1; -- 'size' of moving node (including all it's sub nodes)    -- step 1: temporary "remove" moving node    UPDATE Item    SET leftExtent = 0-(leftExtent), rightExtent = 0-(rightExtent), updatedDate = GETDATE()    WHERE leftExtent >= @moverLeft AND rightExtent <= @moverRight;    -- step 2: decrease left and/or right position values of currently 'lower' items (and parents)    UPDATE Item    SET leftExtent = leftExtent - @node_size, updatedDate = GETDATE()    WHERE leftExtent > @moverRight;    UPDATE Item    SET rightExtent = rightExtent - @node_size, updatedDate = GETDATE()    WHERE rightExtent > @moverRight;    -- step 3: increase left and/or right position values of future 'lower' items (and parents)    UPDATE Item    SET leftExtent = leftExtent + @node_size, updatedDate = GETDATE()    WHERE leftExtent >= CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @node_size ELSE @destinationRight END;    UPDATE Item    SET rightExtent = rightExtent + @node_size, updatedDate = GETDATE()    WHERE rightExtent >= CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @node_size ELSE @destinationRight END;    -- step 4: move node (and it's subnodes) and update it's parent item id    UPDATE Item    SET        leftExtent = 0-(leftExtent) + CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @moverRight - 1 ELSE @destinationRight - @moverRight - 1 + @node_size END,        rightExtent = 0-(rightExtent) + CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @moverRight - 1 ELSE @destinationRight - @moverRight - 1 + @node_size END,         updatedDate = GETDATE()    WHERE leftExtent <= 0-@moverLeft AND rightExtent >= 0-@moverRight;    UPDATE Item    SET parentId = @destinationId, updatedDate = GETDATE()    WHERE id = @id;END