What is wrong with using 'Not In' in this SQL query?

Question

I have table called BST as shown below:

Here N is value of node of Binary Tree and P is its Parent node. I have to write a query that will determine if a node is a Root Node, Leaf Node or Inner Node. I wrote below SQL query for this:

select N, 
case
when P is null then 'Root'
when N in (select distinct P from BST) then 'Inner'
when N not in (select distinct P from BST) then 'Leaf'
end as type
from BST

However, this is not giving me desired result as last condition for 'Leaf' in Case statement doesn't satisfy for leaf node. I am getting below output in this case:

I have a workaround for now as below query which is giving me expected output:

select N, 
case
when P is null then 'Root'
when N in (select distinct P from BST) then 'Inner'
else 'Leaf'
end as type
from BST

Expected Output:

But I can't figure out what's wrong with the first one. Could someone explain me this?

Answer 1

The problem is because one of your P values is null. Remove this by saying select distinct p from t where p is not null in at least the Not In one of your subqueries

http://sqlfiddle.com/#!6/77fb8/3

hence:

select N, 
case
when P is null then 'Root'
when N in (select distinct P from BST) then 'Inner'
when N not in (select distinct P from BST where p is not null) then 'Leaf'
end as type
from BST

the null P value gets included in the list of distinct values selected, and not in can not determine if a given value of N is equal/not equal to the null coming from the root node of P.

It's somewhat counter intuitive but nothing is ever equal to or not equal to a null, not even null. using = with one side being null results in null, not true and not false

IN can be used to check if a value IS in the list, but not if it's not, if the list includes a null

1 IN (1,2,null) --true
3 IN (1,2,null) --null, not false, null which isn't true
3 NOT IN (1,2,null) --null, not false, null which isn't true

The ELSE form is the way to go here. Or put the disctinct query in as a subquery in the FROM block and do a left join to it

Answer 2

in is a shorthand for a series of = checks. null, is not a value - it's the lack thereof. Whenever applying it to an operator expecting a value (like =, or in), it results in null, which is not "true".

You can think of null as an "unknown" value. I.e. - is an unknown value in a list of values selected from a table? We can't know.

Thus, you have to handle nulls explicitly, as you did in your second query.