Modified preorder tree traversal - finding the next node

Question

Hi,

I have this data:

id | parent_id | lft | rgt | name
=====================================
1  | 0         | 1   | 8   | abc
2  | 3         | 5   | 6   | jkl
3  | 1         | 2   | 3   | def
4  | 0         | 9   | 10  | mnno
5  | 1         | 4   | 7   | ghi

I need to traverse this hierarchy in this order (ids): 1 > 3 > 5 > 2 > 4

How can I achieve this?

Assume that I want to find the next node of node_x.

if (node_x_rgt - node_x_lft == 1) {
    next_node_lft = node_x_rgt + 1;
} else {
    next_node_lft = node_x_lft + 1;
}

This formula works only in some cases (node ids 1,3,5,2). The next node of node 2 should be 4.

Answer 1

With the information you gave all I can advice is to try:

select * from table order by id

btw, the lft and rgt columns for id 4 are outside of the tree, looks like an error?

btw2, if this is homework, please tag it as such.

Edit: version 2 of the question:

These kinds of trees have as invariant that (lft < rgt) for all nodes. If the table contains only 1 root node, sequences can be retrieved by either lft or rgt values, in this case lft still does the trick (but the alternative through rgt in descending order won't):

select * from table order by lft