Last time I introduced the Modified preorder tree traversal algorithm as a method to store relationships between nodes. This time I’ll show you how nodes are inserted into the tree. Note that I’m using MySQL, so you may need to change your queries slightly depending on the DB you’re using.
Consider our tree, introduced last time:
Say you wanted to insert “Boxer” as a child node of Dog. The left/right values for this new node will be 14/15, respectively. Before we can insert, however, we need to make some room: all left/right values greater than 13 need to be incremented by two so we can fit Boxer in (Dog becomes Dog and Cat becomes Cat ).
$sql_lft="UPDATE animals SET lft=lft+2 WHERE lft>13";
$sql_right="UPDATE animals SET rght=rght+2 WHERE rght>13";
$sql_insert="INSERT INTO animals (`node_name`,`lft`,`rght`) VALUES ('Boxer',14,15)";
In order to insert a leaf node (at the same level), you simply use the rght value from a neighbor (or parent node’s lft value in some cases… you should be able to figure-out why).
The trickiest part really isn’t the insert as much as it is writing an algorithm that determines the proper lft/rght values at every point in the hierarchy. There are lots of ways to do it, so I’ll leave it up to your imagination. The best way to understand what’s going on is by trying it yourself. If you get stuck, feel free to ask!
Next time around I’m going to discuss the idea of moving (multiple) nodes within the tree, and a few other little pieces of functionality that should serve you well…