Re: 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