0

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?

  • Please tag your RDBMS. – McNets Jun 4 '17 at 19:36
2

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

  • oh I was making that way harder than it needed to be! Thanks! – Legit Stack Jun 4 '17 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.