SQL - NOT IN

Handling hierarchical data and NULL values in SQL

Binary Tree Nodes | HackerRank

• Table Structure: N represents the value of a node in a Binary Tree, and P is the parent of N.

Sample Input

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

Even though I learned about binary trees in my major, facing this concept inside a relational database table on HackerRank caught me off guard a little.

At first, I wrote what seemed like a highly intuitive query, only to be met with a frustrating error. This article is a brief breakdown of how I have a hard time — the relationship between NOT IN and NULL—and how I resolved it.

Get Minseo Kim’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To solve this, I categorized the nodes into three logical cases:

1. Root Node: Has no parent node, meaning its P value must be NULL.
2. Leaf Node: Cannot be a parent to any other node, meaning its N value will never appear in column P.
3. Inner Node: The remaining nodes that do not fall into cases 1 or 2.

Initial Mistake

Based on that logic, I fired up this query and got an error

SELECT N,
    CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N NOT IN P THEN 'Leaf'
        ELSE 'Inner'
    END
FROM BST
ORDER BY N;

I realized two flaws in my initial approach

1. The Syntax Issue : In SQL, the IN or NOT IN operator expects a set of values, not just a single column identifier from the current row. To check whether N exists anywhere within the entire P column, I needed a subquery: (SELECT P FROM BST).
2. The NULL : Column P contains a NULL value (the Root's parent). In SQL, if a NULL is present inside a NOT IN list, the entire logical operation evaluates to Unknown. This completely breaks the conditional check

The Resolution

To fix this, I used a subquery to generate the proper value set and explicitly excluded NULL values using WHERE P IS NOT NULL.

SELECT N,
    CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N NOT IN (
            SELECT P FROM BST
            WHERE P IS NOT NULL
        ) THEN 'Leaf'
        ELSE 'Inner'
    END
FROM BST
ORDER BY N;

Key Takeaway

Never trust NOT IN when your data contains NULL values. Always filter them out beforehand!