wallpapers
  -animals
    -cats
     -lions
  -birds

screensavers
  -fish
    -sharks
  -water
    -beaches
    -ocean  
categories
  -subcategory
    -subsubcategory    

oh boy, this is so hard to learn for a bigener like me.
i save these notes on my computer regarding this topic, i forgot where i got it from but i hope it helps.

---

Modified Preorder Tree Traversal

---

Now, let's have a look at another method for storing trees. Recursion can be slow, so we would rather not use a recursive function. We'd also like to minimize the number of database queries. Preferably, we'd have just one query for each activity.

We'll start by laying out our tree in a horizontal way. Start at the root node (‘Food'), and write a 1 to its left. Follow the tree to ‘Fruit' and write a 2 next to it. In this way, you walk (traverse) along the edges of the tree while writing a number on the left and right side of each node. The last number is written at the right side of the ‘Food' node. In this image, you can see the whole numbered tree, and a few arrows to indicate the numbering order.

We'll call these numbers left and right (e.g. the left value of ‘Food' is 1, the right value is 18). As you can see, these numbers indicate the relationship between each node. Because ‘Red' has the numbers 3 and 6, it is a descendant of the 1-18 ‘Food' node. In the same way, we can say that all nodes with left values greater than 2 and right values less than 11, are descendants of 2-11 ‘Fruit'. The tree structure is now stored in the left and right values. This method of walking around the tree and counting nodes is called the ‘modified preorder tree traversal' algorithm.

Before we continue, let's see how these values look in our table:

Note that the words ‘left' and ‘right' have a special meaning in SQL. Therefore, we'll have to use ‘lft' and ‘rgt' to identify the columns. Also note that we don't really need the ‘parent' column anymore. We now have the lft and rgt values to store the tree structure.

---

Retrieve the Tree

---

If you want to display the tree using a table with left and right values, you'll first have to identify the nodes that you want to retrieve. For example, if you want the ‘Fruit' subtree, you'll have to select only the nodes with a left value between 2 and 11. In SQL, that would be:

---

The returns:

---

Well, there it is: a whole tree in one query. To display this tree like we did our recursive function, we'll have to add an ORDER BY clause to this query. If you add and delete rows from your table, your table probably won't be in the right order. We should therefore order the rows by their left value.

The only problem left is the indentation.

To show the tree structure, children should be indented slightly more than their parent. We can do this by keeping a stack of right values. Each time you start with the children of a node, you add the right value of that node to the stack. You know that all children of that node have a right value that is less than the right value of the parent, so by comparing the right value of the current node with the last right node in the stack, you can see if you're still displaying the children of that parent. When you're finished displaying a node, you remove its right value from the stack. If you count the elements in the stack, you'll get the level of the current node.

If you run this code, you'll get exactly the same tree as with the recursive function discussed above. Our new function will probably be faster: it isn't recursive and it only uses two queries.

---

The Path to a Node

---

With this new algorithm, we'll also have to find a new way to get the path to a specific node. To get this path, we'll need a list of all ancestors of that node.

With our new table structure, that really isn't much work. When you look at, for example, the 4-5 ‘Cherry' node, you'll see that the left values of all ancestors are less than 4, while all right values are greater than 5. To get all ancestors, we can use this query:

Note that, just like in our previous query, we have to use an ORDER BY clause to sort the nodes. This query will return:

We now only have to join the rows to get the path to ‘Cherry'.

---

How Many Descendants

---

If you give me the left and right values of a node, I can tell you how many descendants it has by using a little math.

As each descendant increments the right value of the node with 2, the number of descendants can be calculated with:

descendants = (right – left - 1) / 2

With this simple formula, I can tell you that the 2-11 ‘Fruit' node has 4 descendant nodes and that the 8-9 ‘Banana' node is just a child, not a parent.

---

Automating the Tree Traversal

---

Now that you've seen some of the handy things you can do with this table, it's time to learn how we can automate the creation of this table. While it's a nice exercise the first time and with a small tree, we really need a script that does all this counting and tree walking for us.

Let's write a script that converts an adjacency list to a modified preorder tree traversal table.

This is a recursive function. You should start it with rebuild_tree('Food',1); The function then retrieves all children of the ‘Food' node.

If there are no children, it sets its left and right values. The left value is given, 1, and the right value is the left value plus one. If there are children, this function is repeated and the last right value is returned. That value is then used as the right value of the ‘Food' node.

The recursion makes this a fairly complex function to understand. However, this function achieves the same result we did by hand at the beginning of this section. It walks around the tree, adding one for each node it sees. After you've run this function, you'll see that the left and right values are still the same (a quick check: the right value of the root node should be twice the number of nodes).

---

Adding a Node

---

How do we add a node to the tree? There are two approaches: you can keep the parent column in your table and just rerun the rebuild_tree() function -- a simple but not that elegant function; or you can update the left and right values of all nodes at the right side of the new node.

The first option is simple. You use the adjacency list method for updating, and the modified preorder tree traversal algorithm for retrieval. If you want to add a new node, you just add it to the table and set the parent column. Then, you simply rerun the rebuild_tree() function. This is easy, but not very efficient with large trees.

The second way to add, and delete nodes is to update the left and right values of all nodes to the right of the new node. Let's have a look at an example. We want to add a new type of fruit, a ‘Strawberry', as the last node and a child of ‘Red'.

First, we'll have to make some space. The right value of ‘Red' should be changed from 6 to 8, the 7-10 ‘Yellow' node should be changed to 9-12 etc. Updating the ‘Red' node means that we'll have to add 2 to all left and right values greater than 5.

We'll use the query:

Now we can add a new node ‘Strawberry' to fill the new space. This node has left 6 and right 7.

If we run our display_tree() function, we'll see that our new ‘Strawberry' node has been successfully inserted into the tree:

Food
 Fruit
   Red
     Cherry
     Strawberry
   Yellow
     Banana
 Meat
   Beef
   Pork

Disadvantages

At first, the modified preorder tree traversal algorithm seems difficult to understand. It certainly is less simple than the adjacency list method. However, once you're used to the left and right properties, it becomes clear that you can do almost everything with this technique that you could do with the adjacency list method, and that the modified preorder tree traversal algorithm is much faster. Updating the tree takes more queries, which is slower, but retrieving the nodes is achieved with only one query.
Conclusion

You're now familiar with both ways to store trees in a database. While I have a slight preference for the modified preorder tree traversal, in your particular situation the adjacency list method might be better. I'll leave that to your own judgement.

by Gijs Van Tulder
One last note: as I've already said I don't recommend that you use the title of a node to refer to that node. You really should follow the basic rules of database normalization. I didn't use numerical ids because that would make the examples less readable.

you can go to

Joe Celko Nested Sets nested, nested sets
www.phpclasses.org/browse/package/1374.html

class: joe celko nested sets (nested, nested sets) - php classes
manage tree database structure with celko approach. nested, nested sets. this class is meant to manage tree database structure using jeo celko's nested sets ...
phpclasses.org/browse/package/1374.html - 28k - cached - similar pages - note this
class: nested sets db tree (tree, nested, mysqldump, nested sets ...
manipulate database records in hierarchical trees. tree, nested, mysqldump, nested sets. this class can be used to manipulate nested sets of database table ...
phpclasses.org/browse/package/2547.html - 38k - cached - similar pages - note this
more results from phpclasses.org »
phpdeveloper.org: dotvoid : reordering nested sets using php ...
reordering nested sets using php and javascript. 09.17.2007 at 00:06:00 by raj g. i worked in a similar problem where it was required no only to display but ...
phpdeveloper.org/news/8658 - 16k - cached - similar pages - note this
dotvoid - reordering nested sets using php and javascript
in this model trees are represented as nested sets. instead of using a parentid you have a left and right value for each node expressing the relationship to ...
dotvoid /view.php?id=78 - 19k - cached - similar pages - note this
modeling trees with nested sets and nested intervals
... archives.postgresql.org/pgsql-sql/2003-01/msg00459.php to be clear, i'm not looking ... re: modeling trees with nested sets and nested intervals ...
archives.postgresql.org/pgsql-sql/2006-04/msg00052.php - 15k - cached - similar pages - note this
support for "nested sets" and php (re: recursive select)
prev by date: re: select for update; next by date: re: in-date news items; previous by thread: support for "nested sets" and php (re: recursive select) ...
archives.postgresql.org/pgsql-sql/2002-03/msg00120.php - 13k - cached - similar pages - note this
more results from archives.postgresql.org »
help! my hierarchy is slow - faster hierarchies with nested sets ...
i also stumbled across this php nested sets implementation, which offers a set of functions to maintain (insert, update, etc.) a hierarchy stored as nested ...
kylecordes /2007/08/03/nested-sets/ - 22k - cached - similar pages - note this
hierarchical database trees using nested sets | codeigniter forums
code igniter 1.5.4 / centos 5 / php 5.2.3 / apache 2.2.2 / mysql 5.0.27 ... nested sets are great stuff if you need to use trees and are bound to mysql . ...
codeigniter /forums/viewthread/47671/ - 81k - cached - similar pages - note this
hierarchical database trees using nested sets | codeigniter forums
the nested sets method is most suitable for trees that don’t change very often: ... code igniter 1.5.4 / centos 5 / php 5.2.3 / apache 2.2.2 / mysql 5.0.27 ...
codeigniter /forums/viewreply/232435/ - 81k - cached - similar pages - note this
more results from codeigniter »
extending the nested sets model with "hardlinked nested sets"
the "hardlinked nested sets"-part of the libraries is making good progress. ... a look at this thread: forum.joomla.org/index.php/topic,199298.0.html ...
forum.joomla.org/index.php?topic=189840.5;wap2 - 9k - cached - similar pages - note this
extending the nested sets model with "hardlinked nested sets"
as some of you may know, the nested sets model is a data model for organizing data in tree structures of unlimited depth. this model can be used for almost ...
forum.joomla.org/index.php?topic=189840.0;wap2 - 9k - cached - similar pages - note this
more results from forum.joomla.org »
download joe celko nested sets - joe celko nested sets is meant to ...
download joe celko nested sets - joe celko nested sets is meant to manage tree ... phpsecurityadmin is a php application that was designed to be implemented ...
webscripts.softpedia /script/php-clases/joe-celko-nested-sets-11414.html - 59k - cached - similar pages - note this
download nested sets db tree - nested sets db tree can be used to ...
this class can be used to manipulate nested sets of database table records ... phpsecurityadmin is a php application that was designed to be implemented in ...
webscripts.softpedia /script/php-clases/nested-sets-db-tree-11418.html - 59k - cached - similar pages - note this
more results from webscripts.softpedia »
pear::tree tutorial - php kitchen

this so hard to understand????

hi, my screen name is hostman. im with www.webune.com support.

to help our customer who have dedicated server we are creating this tutorial on how to create this type of algorithym.

Modified Preorder Tree Transversal Totorial

ok this is what i did

STEP 1: CREATE MYSQL DATABASE DUMP:

DISPLAYING

STEP 2: create php file called mptt.php with the following code:

mptt.php

<?
	$db = mysql_connect("HOSTNAME", "USERNAME", "PASSWORD");
	mysql_select_db("DATABASE_NAME",$db);

	$sql = "SELECT title FROM mptt WHERE `left` BETWEEN 2 AND 11";
  	$result = mysql_query($sql ,$db);

  	if ($myrow = mysql_fetch_array($result)) {
  		do {
  			echo $myrow['title'].'<BR>';
  		} while ($myrow = mysql_fetch_array($result));
  	}else{
  		echo '<strong>ERROR: </strong>'.mysql_error();
  	}
  	
?>

NOTE:CHANGE THE FOLLOWING TO YOUR DB CONNECTION SETTINGS:

HOSTNAME (usually localhost)
USERNAME (your database username)
PASSWORD (username password)
DATABASE_NAME (the database where you dump mysql above)


this file will display all file in the FRUIT category

OUTPUT:

INDENTED ORDER DISPLAYING

ok, if you want indent the results so it will be a tree level, you can use this function:

STEP 3: Save this file at mptt-tree.php

mptt-tree.php

PHP / MYSQL Web Hosting at:<br>
<a href="http://www.webune.com"><img src="http://www.webune.com/images/headers/default_logo.jpg" border="0"></a><hr>
<?
	$db = mysql_connect("HOSTNAME", "USERNAME", "PASSWORD");
	mysql_select_db("DATABASE_NAME",$db);

	echo '<hr>'; 
	function display_mptt($root) {
	global $db;
	// retrieve the left and right value of the $root node
	$sql2 = "SELECT * from mptt where id=$root";

	$result2 = mysql_query($sql2 ,$db);
	if(!$row2 = mysql_fetch_array($result2)) echo mysql_error();
	echo '<h1>Indentation</h1>';

	// start with an empty $right stack
	$right = array();

	// now, retrieve all descendants of the $root node
  	$sql = "SELECT * from mptt WHERE `left` BETWEEN ".$row2['left']." AND ".$row2['right']." ORDER BY 'left' ASC";
 	$result = mysql_query($sql ,$db);

 	// display each row
  	while ($row = mysql_fetch_array($result)) {
  		// only check stack if there is one
  		if (count($right)>0) {
  			// check if we should remove a node from the stack
  			while ($right[count($right)-1]<$row['right']) {
  				array_pop($right);
  			}
  		}
 	// display indented node title
  	echo str_repeat('&nbsp;',count($right)).$row['title']."<br>";
 	// add this node to the stack
  	$right[] = $row['right'];
  }
 } 
  
  display_mptt(1);
  ?>

after you save this file and open it with your browser you will see this output:

Indentation
food
  fruit
    red
      cherry
    yellow
      banana
  meat
    beef
    pork

as you can see, it matches our table at the begining of this tutorial.

ADDING

now for the best part, we need to add, so we need to make a webform.

now save this file as mptt-add.php and run in your php website, click on the add link to add to each category. i followed the steps by Gijs Van Tulder

mptt-add.php

PHP / MYSQL Web Hosting at:<br>
<a href="http://www.webune.com"><img src="http://www.webune.com/images/headers/default_logo.jpg" border="0"></a><hr>
<?
	$db = mysql_connect("HOSTNAME", "USERNAME", "PASSWORD");
	mysql_select_db("DATABASE_NAME",$db);
if ($_GET['id']) {
  if(isset($_REQUEST['Submit'])) {
  	$sql = "SELECT * FROM mptt where id=".$_GET['id'];
  	$result = mysql_query($sql ,$db);
  	$row = mysql_fetch_array($result);
  	$right = $row['right'];
  	// UPDATE RIGHT VALUES
  	$sql = "UPDATE mptt SET `right`=`right`+2 WHERE `right` > ". ($right - 1);
  	if(!$result = mysql_query($sql ,$db)) echo "$sql <br>".mysql_error();
  	// UPDATE LEFT VALUES
  	$sql = "UPDATE mptt SET `left`=`left`+2 WHERE `left` > ". ($right - 1);
  	if(!$result = mysql_query($sql ,$db)) echo mysql_error();
  	// INSERT NEW CATEGORY
  	$sql = "INSERT INTO mptt (`left`,`right`,`title`) values ('".$right."', '".($right +1)."', '".$_REQUEST['title']."')";
  	if(!$result = mysql_query($sql ,$db)) echo mysql_error();
  } else {
  	?>
	<form name="form1" method="post" action="<? echo $_SERVER['REQUEST_URI']; ?>">
  	Title: <input type="text" name="title">
	<input type="submit" name="Submit" value="Submit">
	</form>
	<?
  }
  } 
function display_mptt($root) {
  global $db;
  echo '<table border="0" width="200">';
  // retrieve the left and right value of the $root node
  $sql2 = "SELECT * from mptt where id=$root";
  //$sql = "SELECT left,right FROM mptt WHERE `id`=1";
  $result2 = mysql_query($sql2 ,$db);
  if(!$row2 = mysql_fetch_array($result2)) echo mysql_error();
  echo '<h1>Modified Preorder Tree Traversal</h1>';
  // start with an empty $right stack
  $right = array();
 // now, retrieve all descendants of the $root node
  $sql = "SELECT * from mptt WHERE `left` BETWEEN ".$row2['left']." AND ".$row2['right']." ORDER BY 'left' ASC";
  $result = mysql_query($sql ,$db);
 // display each row
  while ($row = mysql_fetch_array($result)) {
  	// only check stack if there is one
  	if (count($right)>0) {
  		// check if we should remove a node from the stack
  		while ($right[count($right)-1]<$row['right']) {
  			array_pop($right);
  		}
  	}
 // display indented node title
  echo '<tr><td>'.str_repeat('&nbsp;&nbsp;',count($right)).$row['title'].'</td><td><a href="'.$_SERVER['PHP_SELF'].'?id='.$row['id'].'">[ add ]</a></td></tr>';
 // add this node to the stack
  $right[] = $row['right'];
  }
  echo '</table>';
} 
  
  display_mptt(1);
  echo "<hr>";
?>
 

EDIT

the next step would be to edit and then to be able to delete..

take a look at this tutorial. it helped me alot

how-to-index-arrays-and-show-all-the-elements-and-values-of-array

this is mysql dump:

this is my function:

i have added a breacrum query so you can display its parents. just go to this post:

breadcrum-modified-pre-order-tree-transversal-mptt-sql-query

by the way, im still working on the editing and deleting part. its more complicated than i thought

good tutorial, doesn't work properly but it gives me the idea of what needs to be done and i can go from here, for example the mptt-add doesn't add correctly and it does not display correctly. mine displays as:

food [ add ]
fruit [ add ]
meat [ add ]
red [ add ]
yellow [ add ]
beef [ add ]
pork [ add ]
cherry [ add ]
banana [ add ]

alright, got it fixed. seems to be an error with mysql when you're using the columns named as 'left' or 'right' so i just changed mine to 'lft' and 'rgt'. if anyone seems to have any issues, contact me and i will help you out. good tutorial hostman! now i will go work on editing and deleting since i pretty much have the idea of it now.