Thread: how to use recursion to find end nodes of a tree

how to use recursion to find end nodes of a tree

From
Date:
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 




Re: how to use recursion to find end nodes of a tree

From
Yasir Malik
Date:
> 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?
>
I haven't programmed in PL/pgSQL in a while, but I'll write some pseudo 
code.  I think the code should be similar:

func(int node)
{   dynamic_array s;   dynamic_array leaves;   int top, count, leaf_id, popped, child;
   leaf_id = top = 0;   s[top] = node;   count = 1;
   // to a depth first search   while(count != 0)   {     popped = s[top];     top--;     count--;
     foreach(select pc.child_id into child from parent_child pc where             pc.parent_id = popped)     {
select* from parect_child pc where parent_id = child;
 
        // a count of zero indicates that child node has no children        if(count_of_above_query = 0)        {
  leaves[leaf_id] = child;          leaf_id++;        }        else        {           // not a leaf, so add it to the
stackfor the next time through           // the loop           top++;           s[top] = child;           count++;
 }     }   }
 
   return leaves;
}

Regards,
Yasir


Re: how to use recursion to find end nodes of a tree

From
Ross Johnson
Date:
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
> 



Re: how to use recursion to find end nodes of a tree

From
Date:
Thankyou very much Yasir and Ross for your help and advice. 
I have created a pl/pgsql version of Yasirs algorithm which
works perfectly, I am also looking into improving efficiency 
by flaging leaf records. Here is my pl/pgsql solution in case
it helps anyone out:

CREATE OR REPLACE FUNCTION parentchildtest(int4) RETURNS _int4 AS
'DECLARE   node ALIAS FOR $1;    s INTEGER[];   leaves INTEGER[];   top INTEGER;   counter INTEGER;   leaf_id INTEGER;
 popped INTEGER;   child RECORD;   childCount RECORD;
 
BEGIN   leaf_id := 0;   top := 0;   s := ''{}'';   leaves := ''{}'';       s[top] := node;   counter := 1;      -- t a
depthfirst search   WHILE (counter <> 0) LOOP    popped := s[top];top := top - 1;counter := counter - 1;
 
FOR child IN SELECT pc.child_id FROM parent_child AS pc    WHERE pc.parent_id = poppedLOOP    SELECT INTO childCount
COUNT(*)AS count FROM parent_child AS pc
 
WHERE pc.parent_id = child.child_id;
    --a count of zero indicates that child node has no children    IF (childCount.count = 0) THEN
leaves[leaf_id]= child.child_id;    leaf_id := leaf_id + 1;    ELSE        -- not a leaf, so add it to the stack for
thenext time
 
through    -- the loop    top := top + 1;    s[top] = child.child_id;    counter := counter + 1;    END IF;END LOOP;
ENDLOOP;
 
   RETURN leaves;
END;' LANGUAGE 'plpgsql' VOLATILE;  

-----Original Message-----
From: Yasir Malik [mailto:ymalik@cs.stevens.edu] 
Sent: 10 April 2006 17:13
To: mike@mikeandems.com
Cc: pgsql-sql@postgresql.org
Subject: Re: [SQL] how to use recursion to find end nodes of a tree


> 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?
>
I haven't programmed in PL/pgSQL in a while, but I'll write some pseudo 
code.  I think the code should be similar:

func(int node)
{   dynamic_array s;   dynamic_array leaves;   int top, count, leaf_id, popped, child;
   leaf_id = top = 0;   s[top] = node;   count = 1;
   // to a depth first search   while(count != 0)   {     popped = s[top];     top--;     count--;
     foreach(select pc.child_id into child from parent_child pc where             pc.parent_id = popped)     {
select* from parect_child pc where parent_id = child;
 
        // a count of zero indicates that child node has no children        if(count_of_above_query = 0)        {
  leaves[leaf_id] = child;          leaf_id++;        }        else        {           // not a leaf, so add it to the
stackfor the next time through           // the loop           top++;           s[top] = child;           count++;
 }     }   }
 
   return leaves;
}

Regards,
Yasir