How to generate a tree view from this result set based on Tree Traversal Algorithm?

Question

I have this table:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL auto_increment,
  `category_id` int(11) default NULL,
  `root_id` int(11) default NULL,
  `name` varchar(100) collate utf8_unicode_ci NOT NULL,
  `lft` int(11) NOT NULL,
  `rht` int(11) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `category_id` (`category_id`),
  KEY `lft` (`lft`,`rht`),
  KEY `root_id` (`root_id`)
) 

Based on this question: Getting a modified preorder tree traversal model (nested set) into a <ul>

The difference is that I have many trees in one table. Each row has a foreign key representing its parent and its top parent: category_id and root_id. Also I have the lft and rht fields based on this example: http://articles.sitepoint.com/article/hierarchical-data-database/2

Based on this rows:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 4, 9);
INSERT INTO `categories` VALUES(4, 3, 1, 'Orange Type 1', 5, 6);
INSERT INTO `categories` VALUES(5, 3, 1, 'Orange Type 2', 7, 8);
INSERT INTO `categories` VALUES(6, 1, 1, 'Pear', 10, 11);
INSERT INTO `categories` VALUES(7, 1, 1, 'Banana', 12, 13);
INSERT INTO `categories` VALUES(8, NULL, NULL, 'Eletronics', 1, 14);
INSERT INTO `categories` VALUES(9, 8, 8, 'Cell Phones', 2, 3);
INSERT INTO `categories` VALUES(10, 8, 8, 'Computers', 4, 9);
INSERT INTO `categories` VALUES(11, 10, 8, 'PC', 5, 6);
INSERT INTO `categories` VALUES(12, 10, 8, 'MAC', 7, 8);
INSERT INTO `categories` VALUES(13, 8, 8, 'Printers', 10, 11);
INSERT INTO `categories` VALUES(14, 8, 8, 'Cameras', 12, 13);

How can I build an ordened list representing this tree?

With the sql bellow:

SELECT c. * , (COUNT( p.id ) -1) AS depth
FROM `categorias` AS p
CROSS JOIN categories AS c
WHERE (
c.lft
BETWEEN p.lft
AND p.rht
)
GROUP BY c.id
ORDER BY c.lft;

I got this result:

As you can see, I need to order by root_id too, so that I can generate the correct tree.

Also, after get the tree, is there a way to order each node by name?

Rhomb

Answer 1

I got it.

All you need to do is set root_id to the top parents too, so that you can ORDER BY correctly.

With the query bellow I can have separeted trees, and uptade only the tree that I'm working on:

SELECT c . * , count( p.id ) AS depth
FROM `categories` c
CROSS JOIN categories p
WHERE (
c.lft
BETWEEN p.lft
AND p.rht
)
AND c.root_id = p.root_id
GROUP BY c.id
ORDER BY c.root_id, c.lft

Rhomb

Answer 2

As you can see, I need to order by root_id too, so that I can generate the correct tree.

When building the nested tree model, never make duplicates on lft and rgt. In fact, you should declare them unique.

In you data model, the sets for category 1 and 8 overlap. Say, 1 to 14 are used both for items 1 and 8.

Replace them with these values:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 4, 9);
INSERT INTO `categories` VALUES(4, 3, 1, 'Orange Type 1', 5, 6);
INSERT INTO `categories` VALUES(5, 3, 1, 'Orange Type 2', 7, 8);
INSERT INTO `categories` VALUES(6, 1, 1, 'Pear', 10, 11);
INSERT INTO `categories` VALUES(7, 1, 1, 'Banana', 12, 13);
INSERT INTO `categories` VALUES(8, NULL, NULL, 'Eletronics', 15, 29);
INSERT INTO `categories` VALUES(9, 8, 8, 'Cell Phones', 16, 17);
INSERT INTO `categories` VALUES(10, 8, 8, 'Computers', 19, 24);
INSERT INTO `categories` VALUES(11, 10, 8, 'PC', 20, 21);
INSERT INTO `categories` VALUES(12, 10, 8, 'MAC', 22, 23);
INSERT INTO `categories` VALUES(13, 8, 8, 'Printers', 25, 26);
INSERT INTO `categories` VALUES(14, 8, 8, 'Cameras', 27, 28);

Now you don't have to order on root_id.

Also, after get the tree, is there a way to order each node by name?

No easy way, unless you insert the nodes in the name order from the beginning. Siblings with the greater name should have greater lft and rgt:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(7, 1, 1, 'Banana', 4, 5);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 6, 11);
INSERT INTO `categories` VALUES(4, 3, 1, 'Orange Type 1', 7, 8);
INSERT INTO `categories` VALUES(5, 3, 1, 'Orange Type 2', 9, 10);
INSERT INTO `categories` VALUES(6, 1, 1, 'Pear', 12, 13);

A nested tree can only have one implicit order.

There is also a way to query adjacency list in MySQL:

• Hierarchical queries in MySQL

, however, you will have to create an additional unique ordering column if you want to order on anything else than id.

You may also want to read this article:

• Adjacency list vs. nested sets: MySQL

which shows how to store and query nested sets more efficiently.

Clayberg

Thanks, I will read this and try. Although, I was wondering if there isn't a way to keep repeated lft and rht since I have a way do distinguish (root_id). I already achieved an query with something like: WHERE root_id =1 OR id =1 ORDER BY lft to get one of the trees (but not all). This is really the wrong way? Also I have the root_id for reference when using the rebuild_tree() method listed on this link articles.sitepoint.com/article/hierarchical-data-database/3 So, everything is working properly except the SELECT for ordened lists. – Rhomb

If I follow your steps, how can I change the rebuild_tree() function to rebuild just one tree and not all? Since I will remove root_id? – Rhomb

If you always separate the trees (like with WHERE root_id = 1) it's OK to allow overlapping between different sets. But your original query mixed two trees. To rebuild only one tree, just call rebuild_tree(1) or rebuild_tree(8), this will only rebuild the trees starting from 1 or 8. – Clayberg

Yes, it's exactly what I'm doing with rebuild_tree($root_id). But, is there a way to continue with this aproach and change my select query so that I can get the whole result separeted by trees, I mean, root_id? Today I can't achieve it because I don't know how to specify this in the query: ORDER BY lft "but group by trees" – Rhomb

@Keyne: try ORDER BY root_id, lft. If you always place Electronics items after Fruits items, mere ORDER BY lft will suffice. – Clayberg

+ 1 for the ORDER BY, thanks. I also have added WHERE c.root_id =p.root_id and now all records are set with root_id, even the top parent. Now everything is working properly. – Rhomb