PostgreSQL Recursive Join – SQL Query for Binary Tree Open List

join;postgresqlrecursivetree

I have a node table that looks like this, plus it has an inserted_at column:

id        |  parent_id
----------+-----------
1         |  nil
2         |  1
3         |  1
4         |  2
5         |  2
6         |  3
7         |  4
8         |  5
9         |  6
10        |  3

It's a representation of a binary tree that looks like this:

             1
          /     \
        2         3
     /   \       /   \
    4    5      10    6
   /     /             \
  7     8               9

I'm trying to write a recursive SQL query that gets a list of nope nodes – nodes that have 1 or 2 open places below them – that is the list of nodes that aren't listed as a parent_id to other nodes 2 times.

This "open_list" would contain 4,5,10,6,7,8,9 because all those nodes have less than two children. So is this possible in SQL? One query that produces the "open list" of a binary tree.

Maybe I'd have to be a recursive CTE table using a WITH statment that some how has a join on itself ?

With recursive (
   select *
   join on self... recursive
)
select * from recursive

That's where my totally amateur intuition goes. Can someone who has a bit more experience guide me to the answer?

Best Answer

In this case I think you don't need a recursive query, simply get those records that do not have two child records.

select *
from   mytable
where  id not in(select   parent_id
                 from     mytable
                 group by parent_id
                 having   count(*) > 1);

id | parent_id
-: | --------:
 4 |         2
 5 |         2
 6 |         3
 7 |         4
 8 |         5
 9 |         6
10 |         3

dbfiddle here

Related Question