MySQL: Find all the leaf nodes of a subtree

Question

I've a tree structure of categories stored in the mySQL table with category_id and parent_id relation. Parent_id = Null corresponds to the root node.

Category (category_id, category_name, parent_id)

What I'm trying to do is to fetch all the leaf nodes give the category_id of a node. I've followed this article. It discusses about getting all the leaf nodes with the below query:

SELECT t1.category_name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent_id
WHERE t2.category_id IS NULL;

But I'm trying to fetch the leaf nodes of a subtree. For example:

In the above structure given node 3 the results will be: 9, 10, 7, 11, 12, 13.

I've also tried the solution given here: adjacency model , given an id return the leaf nodes. But I'm not able to get the desired result.

Can you help me to find a solution?

Answer 1

Oh, well... I happen to have found a solution... It's a little awkward, however:

SELECT TRIM(RIGHT(TRIM(concat_ws(' ',
ifnull(t1.category_id,''),
ifnull(t2.category_id,''),
ifnull(t3.category_id,''),
ifnull(t4.category_id,'')
)),2)) AS leaf_node
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent_category = t1.category_id
LEFT JOIN category AS t3 ON t3.parent_category = t2.category_id
LEFT JOIN category AS t4 ON t4.parent_category = t3.category_id
WHERE t1.category_descr = 'Frames';

It works as long as category_id is < 100, that is, just two digits, but that can be easily adapted. Yes, a completely crazy/awkward/(you name it) solution, but it works for my purposes.

Answer 2

If your leafs are ordered (ie any child is greater than its parent), there's another way:

SELECT tree.id FROM tree
LEFT JOIN tree t1 ON (t1.parent_id = tree.id)
WHERE t1.id IS NULL -- all leafs
AND tree.id > 3 -- greater than starting branch

Answer 3

You can try this script:

Select * from
(SELECT id,name,parent_id FROM
    (SELECT id,name,parent_id,
           CASE WHEN id in (3) THEN @idlist := CONCAT(id)
                WHEN FIND_IN_SET(parent_id,@idlist) THEN @idlist := CONCAT(@idlist,',',id)
                END as checkId
    FROM categories
    ORDER BY id ASC) as T
WHERE checkId IS NOT NULL) N1
left join 
(SELECT id,name,parent_id FROM
    (SELECT id,name,parent_id,
           CASE WHEN id in (3) THEN @idlist := CONCAT(id)
                WHEN FIND_IN_SET(parent_id,@idlist) THEN @idlist := CONCAT(@idlist,',',id)
                END as checkId
    FROM categories
    ORDER BY id ASC) as T
WHERE checkId IS NOT NULL) N2 on N1.Id = N2.Parent_Id

sqlfiddle