What is the difference between modified preorder and just preorder?

Question

I've read about tree traversals and tree data structures so i now know what a preorder tree traversal is, but i also see that there is something called a modified preorder tree traversal but im finding it a little difficult to find good answers or documentation about what the difference between these two are. Can someone comment on that ? I did find an article about explaining it but the diagram looked similar to the regular preorder, the only thing that author wrote was that a node had two additional values, and im not sure if that is correct or not.

The article I read: http://imrannazar.com/Modified-Preorder-Tree-Traversal I also looked through this: http://www.sitepoint.com/hierarchical-data-database-2/ but I'm having a hard time trusting the author who says he is an economics major in college writing about tree structures. Django's mptt module is one place its being used: http://django-mptt.github.io/django-mptt/overview.html#what-is-modified-preorder-tree-traversal

It seems like the modified version of this preorder tree traversal is being used several places when I search on google so I find it a little weird that there aren't more articles that explain the differences.

Answer 1

I disagree slightly with the naming, and perhaps there's some confusion from your side regarding this.

I'd define "traversal" as the process of traversing.

The result we get from the traversal I'd perhaps call a "representation".

MPTT is more of a representation than a traversal.

Additionally, the value on the left can be thought of as preorder, while the value on the right can be thought of as postorder (we'll get to that...).

Thus I might have rather named it "Combined Pre-/postorder traversal representation".

---

Now onto what this actually is.

As mentioned above, it's merely a representation.

Let's look at an algorithm to generate this representation from a tree:

traverse(node, index)
   node.left = index

   for each child c of node
     traverse(c, ++index)

   node.right = ++index

As can be seen with the above code, we do something with the node both before and after recursing to the children, so it can be seen as some combination of pre- and postorder traversal.

Now where the more significant difference between this and pre- or postorder comes in, is how it's used.

Pre- or postorder is typically something you run on a tree or use to generate a tree from (perhaps to compactly store it to disk, while a typical pointer-based representation might be generated in memory when you actually want to use the tree).

But with MPTT, this would be how you actually represent the tree while using it. This is especially useful in databases, which aren't particularly focussed around recursion.

You'd store the MPTT values in your table, and these would allow you to efficiently perform various queries. For example: (derived from here)

• To get all descendants of a node, you'd look for left values between the left and right values of that node.

• To get the path to / all ancestors of a node, you'd look for nodes with left values smaller than this left value and right values greater than this right value.

Both of the above can be performed using a single query, where-as a recursive representation will require one query for each node in the path and ... a few for the descendants.