Hi!
I would like to know how can I display my tree in a horizontal way just like the sample image used in the topic Modified Preorder Tree Traversal.
just like this image without the numbers:
Hello hubster !
I’ve decided to post the reply in the forum so that maybe it can help somebody else too ! 
Okay:
#1 You need to create a column in the table that you can call “link” and that column will be NULL for entries that have no link or will contain the ID of the entry that it’s linked to.
Example:
ID|name|left|right|LINK
1|fruit|1|12|NULL
2|red|2|7|NULL
3|apple|3|4|NULL
4|strawberry|5|6|NULL
5|Delicious|8|11|NULL
6|GHOST LINKED TO STRAWBERRY|9|10|4
so this way you have
fruit
red
[INDENT]apple[/INDENT]
[INDENT]strawberry[/INDENT]
delicious
[INDENT]LINK TO STRAWBERRY[/INDENT]
Then you need that magic MySQL command that gave me a 2 weeks headache:
SELECT table1.*, table2.link as link
FROM food as table1
LEFT JOIN food as table2
ON table1.id=table2.link
WHERE table1.link IS NULL
GROUP BY table1.id
ORDER BY table1.name
Will give you :
id name left right link link
0000003 apple 3 4 NULL NULL
0000005 delicious 8 11 NULL NULL
0000001 fruit 1 12 NULL NULL
0000002 red 2 7 NULL NULL
0000004 strawberry 5 6 NULL 4
Notice that you the category “Strawberry” but not the “Ghost category”
So that was my big pain for the last 2 weeks o if you use this code, don’t be shy to give me credit for it ! :agree:
I hope it was a good explanation !
I have been experimenting using the Modified Preorder Tree Traversal example on sitepoint.
Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork
I was wondering if i could use this example to create a list <ul><li> etc for the output, but then I realised it was a bit more complex than I first thought.
Any thoughts
Nice article. How might you store multiple independent trees? I’d like to avoid introducing a grouping field as it would make moving items between trees messy, plus surely much of the point is that which tree an item belongs to is implicit in knowing who its parent is. What’s more, my trees don’t have any semantic value - they are merely unnamed hierarchical collections with equal status. At present I have the obvious adjacency setup where independent trees are easily identified as they all start with items whose parent id is 0/NULL. Moving items between trees is trivial - just change the parent id pointer in the appropriate child. As far as I can see, the only way to handle this with preordering is to rebuild the two trees involved in their entirety, which can’t be efficient. How can I parallel these operations using the preorder approach?
I had the same question and it was answered here on Sitepoint. 
which level?
please show your table design
Question:
Multi-User issues?
the whole
[quote]
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
INSERT INTO tree SET lft=6, rgt=7, title=‘Strawberry’;
[\quote]
should be locked. which would be very slow. hmm…
how do i get the immediate children of ‘Food’ which are only ‘Fruit’ and ‘Meat’ by SQL?
select title from items where parent = 'Food';
Pretty not-well done.
Page 3 is just sth “i got rid of this article”
The explanation of how adding new nodes is very bad.
Sure explaining the easiest posibility is good, but try to add “Green” to the Fruit Stack. It could be a lot better explained how to get the values for the new node.
uhm, add green to fruit would be : set lft for green value of rgt of fruit, increase all where rgt>=fruit.rgt + 2,set green.rgt to green.lft+1
not that complex, I agree setting parent id of green to fruit is easier, but as mentionned I can be worth the effort to test the performance of both systems…
Does anyone have the code to insert a node, I can’t believe the author of this article left that out. Please Help, I’m so confused.
In playing around, here’s the quick insert_node code I came up with. His description was pretty accurate, and I probably took the long way around a few hurdles, but it works.
function add_node($parent, $title) {
// first, we need to look at the right node of the parent. This will become the left node
// of the new child node (the right node of the new child will be left+1). Thus, the parent
// node’s right value will be right+2. And each node, left or right, of a higher value than
// the parent’s right needs to be incremented by two as well.
// First, get the parent node's right value.
$result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
$row = mysql_fetch_array($result);
$adjVal = $row['rgt']-1;
$newLeft = $row['rgt'];
$newRight = $row['rgt']+1;
// Now, we'll update each node with this right value or greater.
$result2 = mysql_query('UPDATE tree SET rgt=rgt+2 WHERE rgt>'.$adjVal.';');
$result3 = mysql_query('UPDATE tree SET lft=lft+2 WHERE lft>'.$adjVal.';');
// OK, now we just insert the node. Set values as appropriate - $lft to the parent's old $rgt
// and $rgt to the parent's old $rgt+1
$result = mysql_query('INSERT INTO tree (parent,title,lft,rgt) VALUES ("'.$parent.'","'.$title.'",'.$newLeft.','.$newRight.');');
}
OK, I was monkeying around some more, and it’s relatively painless to move a node as well. I think. This is hardly an optimal test database - it has a whopping twenty entries - but enough to get the idea.
function move_node($parent, $title) {
// This is the whack-a-mole method of moving a node (I was too lazy to calculate exactly
// what would be involved in a manual move). So here’s what I do - get the right value
// of the new parent node. Set the parent of the moved node as appropriate. Rebuild the
// database for the current node, then rebuild the entire database. As I say, ugly as sin.
// BUT IT WORKS!!
// First, we get the parent's right value
$result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
$row = mysql_fetch_array($result);
$newLeft = $row['rgt'];
// Maybe we should take the root of the entire tree, and rebuild from that? Easy, but time-consuming.
$result = mysql_query('SELECT title FROM tree ORDER BY lft ASC LIMIT 1;');
$row = mysql_fetch_array($result);
$rootLevel=$row['title'];
// Next, we set the node's new parent.
$result = mysql_query('UPDATE tree set parent="'.$parent.'" WHERE title="'.$title.'";');
// Rebuild the tree from this node down, based on a new left value.
rebuild_tree($title, $newLeft);
// Rebuild the entire DB, because you just clobbered the hell out of it!
rebuild_tree($rootLevel, 1);
}
… The real disadvantage to this approach is the double-rebuild of the database. I probably don’t have to do it, but I figure better safe than sorry. Please do post a quicker or more efficient way of moving nodes, if anybody has one…
This is good if you have 1 Tree per table.
Im wondering, how do you solve the issue if you have multiple trees with different roots?
i mean, for instance drive MyComputer.
ID,Name,ParentID
1, DriveC, 0
2, DriveD, 0
3, DriveE, 0
4, Documents,2
5, Winnt, 2
6, Downloads, 2
I was having a hardtime applying this concept. this can easily be solve by creating a super root, and all multiple trees point to this. but still the problem is, how to solve the multiple tree problem? help
This is a great article and one major positive I see for the Modified Preorder Tree Traversal method is the inbuilt ordering of elements within the same level on the tree.
Jerry - they aren’t multiple trees, and you aren’t adding a super-root: you’re looking at each physical drive as a tree in and of itself, while Micro$oft, for example, looks at ‘My Computer’ as the root node, each drive as a child node, and so on. A cubicle jockey might decide that the cubicle cluster should be the root, and each computer a child, and each drive a child of that. A corporate IT guy might look at the entire company’s network as a root node, and each cubicle cluster as a child, and so on. Ad nauseam.
And falieson, as I said in your thread in the forums, simply rebuilding the tables resolved that – problem.
On to more fun - I have built a delete_node() function. Basically, it reverses the add_node() - it removes the node and all descendants, then decrements all nodes with a greater lft and rgt value as appropriate. Here’s the code for THAT:
function delete_node($title) {
// This will delete a node AND ALL DESCENDANT NODES! If this isn’t what you want,
// consider moving all sub-nodes out first. Alternatively, I can rewrite this to
// remove only the node, and change the nlevel of all child nodes to point to the
// deleted node’s parent. However, this strikes me as slightly counter-intuitive.
//
// Logically, I think that the process will be similar to that of adding a node, only
// in reverse. First, we’ll need to get the left and right value of the node to be
// removed. When we have this, we’ll run a delete to remove any node whose left and
// right fall between these values (inclusive, to remove the node itself). Then, we
// need to decrement all left and right node values by the difference between the
// deleted node’s right and left values, plus one.
// First, get the right/left from the selected node.
$result = mysql_query('SELECT rgt, lft from tree WHERE title="'.$title.'";');
$row = mysql_fetch_array($result);
$leftVal = $row['lft'];
$rightVal = $row['rgt'];
$decrementBy = $rightVal - $leftVal + 1;
// Now, we have the range of nodes to be deleted.
$result = mysql_query('DELETE FROM tree WHERE lft BETWEEN '.$leftVal.' AND '.$rightVal.';');
// If this is right, we should decrement all remaining nodes with a left and/or right
// greater than the deleted node's right value by our $decrementBy value. I think.
$result2 = mysql_QUERY('UPDATE tree SET rgt=rgt-'.$decrementBy.' WHERE rgt>'.$rightVal.';');
$result3 = mysql_QUERY('UPDATE tree SET lft=lft-'.$decrementBy.' WHERE lft>'.$rightVal.';');
// And that should do it.
}
thanx.
i was about to implement this idea but
the difficult part was populating the values of left and right numbers.
i realize that i have multiple trees.
how to populate the left and right values when using different trees?
the only solution i see now is to add a supernode(my computer being top most root or other reserves superroots. hehe) the so that i can populate the left and right values.
i’ll be implementing this soon as soon as i clean up the database.
Is there really a need of left and right value?
Why do we need the left and right?
Isn’t just the parent sufficient?
The point of the left and right is kind of obscure, REMIYA, but it is practical. Typically, when querying a database for a given node and it’s descendants, you get the parent, then all nodes that point to that parent, then, for each child, you get all the nodes that point to that child, and so on, and so on… But with the left-right values, asking for any left/right values between a given node will return ALL of its descendants. And ordering them by left value will put them into a recognizable tree. If you want to know more, I’m actually building a PHP5 class to do all this for you. The end user should NEVER see the left and right value, it’s purely an internal data representation tool.
Just email or IM if you have questions about this - I’m really enjoying this!