how to use recursion to find end nodes of a tree

From: <mike(at)mikeandems(dot)com>
To: <pgsql-sql(at)postgresql(dot)org>
Subject: how to use recursion to find end nodes of a tree
Date: 2006-04-10 15:09:57
Message-ID: 000201c65cb0$d8a6fe20$0100a8c0@xphome
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-sql

Hello All,

I have been having a really hard time trying to come up with a pl/pgsql
recursive function to returns the end nodes of a tree.
Here is an example table definition:

CREATE TABLE parent_child (
parent_id integer NOT NULL,
child_id integer NOT NULL
);

INSERT INTO parent_child (parent_id, child_id) VALUES (1, 2);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 3);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 4);
INSERT INTO parent_child (parent_id, child_id) VALUES (2, 5);
INSERT INTO parent_child (parent_id, child_id) VALUES (2, 6);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 7);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 8);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 9);
INSERT INTO parent_child (parent_id, child_id) VALUES (9, 10);

This produces the following tree of data:

1
___|___
| | |
2 3 4
_|_ _|_
| | | | |
5 6 7 8 9
|
10

I want to create a function that returns the terminating nodes of
of this tree below a certain level i.e. if I input 1 to the function
I need it to return 5,6,3,7,8,10. If I input 4 to the function I would
get 7,8,10. I have written recursive functions which return all nodes
on a branch of a tree but I can't think of a way to return the end nodes
does anyone know of a solution?

Many thanks,

Mike

Responses

Browse pgsql-sql by date

  From Date Subject
Next Message codeWarrior 2006-04-10 15:10:47 Re: Returning a set from an function
Previous Message FavoYang 2006-04-10 03:44:34 slow 'IN' clause