Search code examples
mysqlsqlsubquerycasehierarchical-data

Am I using "NOT IN" correctly?

I'm trying the HackerRank problem linked here.

I'm curious as to why my attempted solution does not return any rows for the binary tree's leaves. Here's my full query:

SELECT N, 'Root'
FROM BST
WHERE ISNULL(P)

UNION

SELECT N, 'Inner'
FROM BST
WHERE N IN (SELECT P FROM BST) AND NOT ISNULL(P)

UNION

SELECT N, 'Leaf'
FROM BST
WHERE N NOT IN (SELECT P FROM BST)

ORDER BY N

It seems to me like my approach to identifying the leaves is correct - a leaf is defined as a node that is not a parent. However, when I try the SELECT N, 'Leaf' ... query on its own, I get no output.

Can anyone spot my error? Am I using the NOT IN statement correctly?

edit: Just to clarify, N is the value of the node, and the corresponding P is its parent. N and P are both integers.

Solution

  • If you run the leaf query, you get nothing:

    mysql> select n, 'Leaf' from bst where n not in (select p from bst);
Empty set (0.00 sec)

    The reason is that the result of the subquery includes NULL:

    mysql> select distinct p from bst;
+------+
| p    |
+------+
| NULL |
|    1 |
|    3 |
|    4 |
+------+

    The comparison N not in (NULL, 1, 3, 4) is bound to return no matches, because of the NULL. This is equivalent to:

    WHERE NOT (N = NULL OR N = 1 OR N = 3 OR N = 4)

    But any comparison to NULL is NULL, not false. You can get true/false for the other terms, but not the first term. This simplifies to:

    WHERE NOT (NULL OR FALSE OR FALSE OR FALSE)

    Which in turn simplifies to:

    WHERE NOT (NULL)

    But the negation of NULL is also NULL, not true. Therefore the condition in your query is bound to block out all nodes, whether they are leafs or not.

    You can fix this by eliminating the NULLs:

    mysql> select n, 'Leaf' from bst where n not in (select p from bst where not isnull(p));
+---+------+
| n | Leaf |
+---+------+
| 2 | Leaf |
| 5 | Leaf |
| 6 | Leaf |
+---+------+

    You should also look into using recursive CTE queries in MySQL 8.0 if you have this sort of data:

    WITH RECURSIVE cte (N, Label) AS
( 
  SELECT bst.N, CAST('Root' AS CHAR(20)) FROM bst WHERE ISNULL(P)
  UNION ALL
  SELECT bst.N, IF(below.P IS NULL, 'Leaf', 'Inner') FROM bst JOIN cte ON bst.P=cte.N
  LEFT OUTER JOIN bst AS below ON bst.N=below.P
)
SELECT DISTINCT N, Label FROM cte

+------+-------+
| N    | Label |
+------+-------+
|    1 | Root  |
|    2 | Leaf  |
|    3 | Inner |
|    4 | Inner |
|    5 | Leaf  |
|    6 | Leaf  |
+------+-------+