Recursively find the path to all leaves descending from a given parent in a tree

All we need is an easy explanation of the problem, so here it is.

I’m trying to write a query to identify the path to each furthest descendant of a particular parent node in a table of tree structures like:

    0     1
    |     |
    2     3
    |     |
    4     5
   / \    |
 *6*  8  *7*
      |
     *9*

There are many parents, all children have one parent, parents have 0-5 children (but the graph is very "long" – most parents only have one child). There are no cycles.

I’m trying to efficiently identify the path to the furthest descendants of a specific node (and not to any intermediate nodes). E.g. in the above:

  • get_leaf_paths(1) would return 1 row: {1, 3, 5, 7}
  • get_leaf_paths(2) would return 2 rows: {2, 4, 6} and {2, 4, 8, 9}

Sample table:

CREATE TABLE graph (
    id bigint PRIMARY KEY,
    parent_id bigint,
    FOREIGN KEY (parent_id) REFERENCES graph(id)
);
INSERT INTO graph (id, parent_id)
    VALUES (0, NULL),
           (1, NULL),
           (2, 0),
           (3, 1),
           (4, 2),
           (5, 3),
           (6, 4),
           (7, 5),
           (8, 4),
           (9, 8);

I’m hoping for a result that looks something like:

SELECT get_leaf_paths.* FROM get_leaf_paths(0);
path
-----
{0, 2, 4, 6}
{0, 2, 4, 8, 9}
(2 rows)

In my initial attempt at a function with a recursive query, I’ve had trouble selecting only the furthest leaves, especially since some branches are shorter than others (e.g. 6 and 9 above are at different depths). The paths can be very deep (thousands or millions of elements), so I would also like to avoid the excessive memory usage of generating paths for every intermediate node.

Any ideas would be greatly appreciated. Thanks!

How to solve :

I know you bored from this bug, So we are here to help you! Take a deep breath and look at the explanation of your problem. We have many solutions to this problem, But we recommend you to use the first method because it is tested & true method that will 100% work for you.

Method 1

WITH RECURSIVE
cte AS ( SELECT id, 
                parent_id, 
                id::TEXT path,
                NOT EXISTS ( SELECT NULL
                             FROM graph gr
                             WHERE graph.id = gr.parent_id ) is_leaf
                FROM graph 
                WHERE id = 2 /* initital node id */
         UNION ALL
         SELECT graph.id, 
                graph.parent_id, 
                cte.path || ',' || graph.id,
                NOT EXISTS ( SELECT NULL
                             FROM graph gr
                             WHERE graph.id = gr.parent_id ) 
         FROM cte JOIN graph ON cte.id = graph.parent_id)
SELECT path 
FROM cte
WHERE is_leaf

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2e40ff454f302033bf5e8cba8b0b0d85

Multiple initial nodes may be applied too (WHERE id IN (0, 1)).

Note: Use and implement method 1 because this method fully tested our system.
Thank you 🙂

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply