Query furthest children in Adjacency List

Question

So I have an SQL query to retrieve all the children of a given node in an adjacency list.

WITH    RECURSIVE
        q AS
        (
        SELECT  id, name
        FROM    categories h
        WHERE   id = 11846801
        UNION ALL
        SELECT  hc.id, hc.name
        FROM    q
        JOIN    categories hc
        ON      hc.parent = q.id
        )
SELECT  name
FROM    q

Is there a way to modify this query to return me just the bottom level of nodes? I can't just specify a given level as each path may have a different depth.

Answer 1

Interpretation 1

"All leave nodes with the longest path from the start."

One way would be to count the levels on your way down and only return members of the bottom one:

WITH RECURSIVE q AS (
   SELECT  id, name, 0 AS lvl
   FROM    categories
   WHERE   id = 11846801

   UNION ALL
   SELECT  c.id, c.name, q.lvl + 1
   FROM    q
   JOIN    categories c ON c.parent = q.id
   )
SELECT  id, name
FROM    q
WHERE   lvl = (SELECT max(lvl) FROM q);

Interpretation 2

"All leave nodes."

WITH RECURSIVE q AS (
   SELECT  id, name, parent
   FROM    categories
   WHERE   id = 11846801

   UNION ALL
   SELECT  c.id, c.name, c.parent
   FROM    q
   JOIN    categories c ON c.parent = q.id
   )
SELECT  id, name
FROM    q
WHERE   NOT EXISTS (SELECT FROM q q1 WHERE q1.parent = q.id);

It should be faster to check on q than on the base table - unless q is very big, in which case indexes on the main table may be faster.