1

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:

enter image description here

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;
Salman A
  • 262,204
  • 82
  • 430
  • 521
user_12
  • 1,778
  • 7
  • 31
  • 72

2 Answers2

2

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)
Salman A
  • 262,204
  • 82
  • 430
  • 521
  • So if I have NULL then `NOT IN` won't work ? If I have NULL will `IN` works? – user_12 Oct 21 '21 at 11:03
  • 1
    Additional clarification... `1 IN (null, 1)` returns true, `2 IN (null, 1)` returns unknown, so this kind of produces the _expected_ result when used inside WHERE/WHEN clause. But `1 NOT IN (null, 2)` returns unknown where you would be _expecting_ true since 1 does not exist in the set. – Salman A Oct 21 '21 at 11:34
1
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).

Akina
  • 39,301
  • 5
  • 14
  • 25
  • Thank you for this approach. Can you break the query down and explain how its working, I am not able to understand it – user_12 Oct 21 '21 at 11:02
  • @user_12 `t1.p IS NULL` checks does the node is a root (R, can be 0 or 1). `EXISTS` checks does the node is a leaf (L, can be 0 or 1). Then I calculate `1 + 2*R + L` which can be from 1 to 4. `ELT` selects according value by this calculated expression. That's all. PS. EXISTS with correlated subquery is more fast then WHERE IN in most cases (of course suitable index must present). – Akina Oct 21 '21 at 11:05