Reply-To: <mike@mikeandems.com>
From: <mike@mikeandems.com>
To: <pgsql-sql@postgresql.org>
Subject: how to use recursion to find end nodes of a tree
Date: Mon, 10 Apr 2006 16:09:57 +0100
Message-ID: <000201c65cb0$d8a6fe20$0100a8c0@xphome>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
Importance: Normal

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