Modified Preorder Tree Traversal

Display mode

Back to Articles

The MPTT algorithm is, as the name states, a modification of pre-order tree traversal; each node of the tree has two extra values associated to it, to assist in the traversal of the tree.

Data structure

Node IDNameLeft MPTT valueRight MPTT value
1(Root)116
2Articles211
5Fiction38
7Fantasy45
8Sci-fi67
6Reference910
3Portfolio1213
4Contact1415
SELECT * from Pages order by mpttLeft asc
Figure 1: Sample MPTT tree

Numbers are assigned such that a path can be traced around the tree, taking in every node. The path here starts at (Root), flowing down the left, around the bottom of the Fiction subtree, then up to the Reference branch of Articles, and from there to the other branches of (Root), before flowing back to (Root).

Note that leaf nodes (those with no children) have Left and Right values immediately after each other; Portfolio, for example, is 12/13. Note also that the parent of a node has a smaller Left and a bigger Right; this can be used to trace up the tree finding parent nodes, until you hit a Left of 1 (meaning the root node). For example, Fantasy (4/5) has a parent of Fiction (3/8), which has a parent of Articles (2/11).

Operations

Addition
To add a node, simply add 2 to all the values after that node, then insert the node into place. As an example, inserting a "Horror" section under Fiction is a simple matter of:
  • Finding where to insert "Horror" (after 7)
  • Adding 2 to every Left value past 7
  • Adding 2 to every Right value past 7
  • Inserting a new row, "Horror", with Left=8 and Right=9
At the end of this, "Fiction" would have a Left of 3 and Right of 10.
Removal
A very similar process is used to delete a node from the tree. For example, to delete "Fantasy":
  • Fetch the Right value of the node (in this case, 5)
  • Subtract 2 from every Left value past 5
  • Subtract 2 from every Right value past 5
  • Remove the node row