How to use NOT IN in binary tree problem using MySQL

I am trying to solve this problem,

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.

Input:

Desired Output:

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

This is my query, can anyone tell me why it’s not working?

select case
            when P is NULL then CONCAT_WS(" ", N, 'Root')
            when N not in (SELECT DISTINCT P FROM BST) then CONCAT_WS(" ", N, 'Leaf')
            else CONCAT_WS(" ", N, 'Inner')
        end
from BST ORDER BY N ASC;

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 1

You have NULL inside the P column in which case an expression such as:

1 NOT IN (NULL, 2, 8, 5)

will return unknown instead of the “expected” result true (ref).

The solution is to make a subtle change like so:

N NOT IN (SELECT P FROM BST WHERE P IS NOT NULL)

Or use an EXISTS query:

NOT EXISTS (SELECT * FROM BST AS bst2 WHERE bst2.P = bst.N)

Method 2

SELECT n,
       ELT((1 + (2 * (t1.p IS NULL)) + (EXISTS (SELECT NULL FROM BST t2 WHERE t1.n=t2.p))), 'Leaf', 'Inner', 'Single', 'Root') type
FROM BST t1
ORDER BY n;

https://dbfiddle.uk/?rdbms=mysql_8.0&fiddle=287b1de2b2bb532d73619c19bcf8a86b

I add one more option ‘Single’ – the case when the node is root and leaf at the same time (node 4 in my fiddle).

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0