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?

Improve this question
1
  • Please tag your RDBMS. Commented Jun 4, 2017 at 19:36

1 Answer 1

Reset to default
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

Improve this answer
1
  • oh I was making that way harder than it needed to be! Thanks! Commented Jun 4, 2017 at 19:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.