Oh, I recognise the left/right thing; the idea is that all the subcategories of a give category have a left value greater than its parent's, and a right value that's less. It makes updating and inserting a fair bit slower, because it involves changing half the rows in the table on average, but for static lists it simplifies the task of locating the subtree of a given node to a simple pair of < > comparisons.
The upshot of this is that if the list of categories is sorted by left, then the first record is the root node of the tree; and all nodes in all subtrees have left values greater than any right value of subtrees to the left.
So if you're going through the rows and come across a right value larger than the right value of the row you've just seen, then it means you've started moving back up the hierarchy. Keep doing that until you find a record where left is larger than the previous right, because that's where you start moving down again.
So: sort the results by left, and create an (empty) array of right values. As you go through each row, check its right value with the one on the top of the stack. If the one on the stack is larger, you're still going down the hierarchy, so push the current row's value on to it. If the top value on the stack is less than the current one, then pop it off and check again.
The point of the stack in the previous paragraph is that the number of elements in the stack is the same as the depth of the current node in the hierarchy: so every time you push a new value on to the stack you're starting a new "sub" of the current sub-category (a new <ul>, say). And every time you pop one off, you're finishing a "sub" (</ul>).
