Sooner or later, any application needs a way to categorize data, and categories must be stored in a tree, because each category has a parent and possibly subcategories. A category without a subcategory is a leaf of the tree. If there are categories without a parent, we create a fictitious root tree node, and append all of them as subcategories of the root.
The main issue is how to store categories with parent-child relations in a database table, and efficiently add nodes and queries for ancestors and descendants of a node.
This can be done using a modified pre-order tree traversal algorithm, described as follows.
The key trick consists of storing each node in its own record with two integer attributes, left and right, so that all its ancestors have a left attribute lower than or equal to the left attribute of the current node, and a right attribute larger than the one of the current node. Similarly, all descendants will have a left larger or equal than...