Subject: Re: how to use recursion to find end nodes of a tree
From: Ross Johnson <ross.johnson@homemail.com.au>
To: mike@mikeandems.com
Cc: PostgreSQL SQL List <pgsql-sql@postgresql.org>
In-Reply-To: <000201c65cb0$d8a6fe20$0100a8c0@xphome>
References: <000201c65cb0$d8a6fe20$0100a8c0@xphome>
Content-Type: text/plain
Date: Tue, 11 Apr 2006 09:57:34 +1000
Message-Id: <1144713454.8841.485.camel@desk.home>
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit

On Mon, 2006-04-10 at 16:09 +0100, mike@mikeandems.com wrote:
> 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);
> 

What you appear to have is really this, with a missing first node:

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

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

This makes it easy to search from leaf to root, but not from root to
leaf. Without a list of child_ids in each node you must search the whole
table for nodes that have the current node id as their parent_id in
order to determine if a node is a leaf node or not. Perhaps you can
include a child_id[] in each node, or a has_children boolean flag that
you set and unset when inserting or deleting rows.

But perhaps you can get PostgreSQL to do it for you by setting
this_node_id as primary key and parent_id as foreign key referencing
this same table. You could then test if it's a leaf node by attempting
to change the node's this_node_id to some out-of-range value and see if
it produces as error. If no error then it's a leaf node, (then you must
restore this_node_id - I would try just negating it for the test, so I
don't have to actually store the original value somewhere).

> 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 
> 
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
> 
>                http://archives.postgresql.org
>