Creating a tree from a list of tuples

Question

I seem to be blind at the moment, so I need to ask here. I want to sort a list of tuples which look like that

(id, parent_id, value)

So that it is a representation of the tree as a flattend list of list of tree nodes.

For example the input

(1, None, '...')
(3, 2', '...')
(2, 1, '...')
(4, 1, '...')
(5, 2, '...')
(6, None, '...')

Should sorted like that afterwards

(1, None, '...')
(2, 1, '...')
(3, 2', '...')
(5, 2, '...')
(4, 1, '...')
(6, None, '...')

Any hint would be highly appreciated. Thanks in advance.

Answer 1

I'm not sure I've quite follows what you are exactly trying to do, but if you have a forest as a list of nodes, can't you just read it and build the tree structure, then write it out as a bread-first traversal of all the trees? Any particular reason to avoid this?

Answer 2

Oliver, if I understand correctly, I think you can either (a) retrieve all tuples from your database into a dictionary or list, and then construct the tree, OR (b) use an ORDER BY clause when you retrieve the tuples so that they are in the order in which you will add them to the tree.

If changes to the tree may be made in your application and then propagated to the database, I would opt for a, but if changes are always made as database inserts, updates or deletes, and apart from these your tree is read-only, then option b should be faster and require less resources.

Roland