Convert flat data into a hierarchical python list

Question

I have a data model from my database. This is a flat python list sorted by left values.

>     id    name  left right
>     1 Beginning 1 6
>     2 FOO  2 5
>     3 BAR  3 4
>     4 Programming 6 13
>     5 Python  7 8
>     7 C#  9 12
>     8 XNA  10 11
>     6 About  14 15

I would like to compute this into a hierarchical python list, that in turn will be converted to HTML/XML as a unordered list. The python list with be a lists within lists.

Example

categories = [
   ["programming", [
                      ["Python", ["pygame"]],
                      ["C#", ["XNA"]],
                   ]
   ],
   ["FOO", [
               ["BAR"]
           ]
   ],
]

Answer 1

This is a modified pre-order tree traversal.

http://www.sitepoint.com/print/hierarchical-data-database/

So the input looks like this, a list of dictionaries.

dbrows = [
   {'title': 'Food', 'lft': 1, 'rgt': 18},
   {'title': 'Fruit', 'lft': 2, 'rgt': 11},
   #etc... etc... from the linked article.
]

Using the fruit input from the linked article. This is what I want, sorted as a python list.

tree = [
        ['Food', [
             ['Fruit', [
                   ['Red', ['Cherry', 'Strawberry']],
                   ['Yellow', ['Banana']],
             ]],
             ['Meat', [
                   ['Beef', 'Pork']
             ]],
        ]],
]