views:

153

answers:

1

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.

A: 

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
rsp
Thanks rsp. Actually, yes id 4 is a separate tree. Id 2 is the last node of tree of node id 1. If I request the next node of id 2, it should give me the first nod of next tree (tree of node id 4).
matte
How ordering by id can help me? And also this is not a homework :)
matte
Ordering by id helped in the 1st version of the question where the requested order was 1,2,3,4,5 :-)
rsp
ohh ok, well that was not the correct order I wanted :)
matte
Is this better?
rsp
yes, i think this solves the "next node" problem. But as you have said "...but the alternative through rgt in descending order won't...", this doesn't work for finding previous node, right?
matte
rsp, how about if i put all trees under one root node?
matte
rsp, forget about the previous node question. noticed that i can use the same lft ordering to retrieve the previous node.
matte
for future reference, to find next node: "SELECT * FROM table WHERE lft > %s ORDER BY `lft` ASC LIMIT 1" and to find previous node "SELECT * FROM `pages` WHERE lft < %s ORDER BY `lft` DESC LIMIT 1" where %s is the node that next and previous node to be found. Thanks rsp.
matte