Modified preorder tree traversal - determining the "top" when no parent is specified

Question

I'm implementing a Modified preorder tree traversal class for a category tree on a Web site, but I'm having trouble with one scenario. Typically when inserting a new category a top-level parent is specified, whose left value in the tree is used in order to determine where the new category should go in the tree. However, there could be times when no parent is specified, which means the new category must go in at the top of the tree, to the right of any other categories at the top of the tree.

Looking at some other applications with similar structures, many of them seem to be inserting a "root" node in the tree at the time of installation. I'm wondering if this is so they don't ever have to detect if it is the first insert, and they always have a left reference. Any thoughts or pseudo-code would be much appreciated. I'm doing this in PHP if it matters. My tree might look something like this:

Electronics         Apparel         My New Category
    / \               / \
MP3     TVs    Shirts     Shoes

My thought is that in this scenario, Apparel's right value will always be the greatest in the table, but I'm not sure how I might use that to determine it is the last. Any help or hints would be appreciated.

Answer 1

In the example you've presented, Electronics and Apparel are technically two separate trees if they have no common parent. If you add "My New Category" it's also a new tree. If you're trying to traverse between Electronics, Apparel and My New Category you need a value above all three, say "All" that is your root node.

See Storing Hierarchical Data in a Database for a example with both a enumerated tree and examples or actual storage in the database.

Answer 2

Another very efficient way of storing that kind of data is using Nested Sets, it allows many common operations with just one query, and eliminates the need for recursion of other schemes.

Answer 3

When inserting. Run a query, ordered by LEFT, take the last one, that is your last root category, call it last_tree. When inserting your new tree, give it a left value of last_tree + 1 and right value of last_tree + 2.

Take a look here for a cakephp example:

http://bakery.cakephp.org/articles/view/modified-preorder-tree-traversal-component