binary tree nodes sql hackerRank question

Question

I am trying to solve below question of hackerrank : You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N. Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node: Root: If node is root node. Leaf: If node is leaf node. Inner: If node is neither root nor leaf node.

I am getting output if i use "IN" operator in second Case but not getting output if i am using "NOT IN" could anyone please tell why it is not executing second case

select n,
case
when p is null then "Root"
when N  IN (select p from bst) then "Inner"
else "Leaf"
end
from bst
order by n

case
when p is null then "Root"
when N NOT IN (select p from bst) then "Leaf"
else "Inner"
end

Answer 1

I am using Oracle DB and Oracle uses ANTI JOIN for NOT IN.

However NOT IN is semantically different from the LEFT JOIN / IS NULL and NOT EXISTS. Since its logic is trivalent and filtering on, it will never return anything if there are NULL values in the list. That's why you are not getting output.

Instead you can use EXISTS / NOT EXISTS to solve it:

select N,
case
    when p is null then "Root"
    when NOT EXISTS (select p from bst b where b.p=a.n) then "Leaf"
    else "Inner"
end
from bst a
order by n;