How can I recursively query a table containing LTREE to get the tree like structure when some of the parent paths are missing?

Question

Lets say I have this table:

CREATE TABLE nodes (node_path ltree);
INSERT INTO nodes VALUES ('Top.Science');
INSERT INTO nodes VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO nodes VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO nodes VALUES ('Top.Hobbies');
INSERT INTO nodes VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
INSERT INTO nodes VALUES ('Top.Dislikes');
CREATE INDEX ON nodes USING GIST (node_path);
CREATE INDEX ON nodes USING BTREE (node_path);

Notice that following paths are missing in this table:

'Top'
'Top.Science.Astronomy'
'Top.Collections'
'Top.Collections.Pictures'

How can I recursively query this table to get the tree like structure (without those missing rows)?

If the paths were not missing, then the following query would get me the result:

with recursive
base as (
  select node_path, 
         array[row_number() over (order by node_path)] as sort_path
    from nodes 
   where nlevel(node_path) = 1
  union all
  select c.node_path, 
         p.sort_path||row_number() over (order by c.node_path)
    from base p
    join nodes c 
      on subpath(c.node_path, 0, -1) = p.node_path
)
select * from base order by sort_path;

But because the rows are missing, it breaks the chain. As a result, things like:

nlevel(node_path) = 1

subpath(c.node_path, 0, -1) = p.node_path

don't make sense.

How can I query this to get the tree?

Note that I posted a question on Stack Overflow and I think if I can get an answer to the above question, then I might be able to resolve my SO question too. This current question was born out of the SO question:

https://stackoverflow.com/questions/76658570/postgres-ltree-how-to-do-recursive-for-only-a-few-specific-rows

Answer 1

This is a possible solution:

WITH RECURSIVE cte AS (
      SELECT n1.node_path,
             1 AS level
      FROM nodes AS n1
      WHERE NOT EXISTS (SELECT FROM nodes AS n2
                        WHERE n2.node_path @> n1.node_path
                          AND n2.node_path <> n1.node_path)
   UNION ALL
      SELECT c.node_path,
             cte.level + 1
      FROM cte
         CROSS JOIN LATERAL (SELECT n1.node_path
                             FROM nodes AS n1
                             WHERE n1.node_path <@ cte.node_path
                               AND n1.node_path <> cte.node_path
                               AND NOT EXISTS (SELECT FROM nodes AS n2
                                               WHERE n1.node_path <@ n2.node_path
                                                 AND n2.node_path <@ cte.node_path
                                                 AND n2.node_path <> n1.node_path
                                                 AND n2.node_path <> cte.node_path)
                            ) AS c(node_path)
)
SELECT * FROM cte;

I start with the nodes that have no ancestor, and in the recursive step I find direct descendants (with no shorter intermediate descendant).