Binary tree "get open list" SQL query

Question

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?

• McNets: Please tag your RDBMS.

Answer 1

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

• MetaStack: oh I was making that way harder than it needed to be! Thanks!