Search code examples
sql-servertree

LeetCode [Tree Node] - What is wrong with my T-SQL query?

A link to the challenge is here. There is a Tree table with two columns - id and p_id, and you are asked to categorize each node id as a root, inner or leaf. The tree has one root node (with p_id aka parent id = null), and inner nodes are those with parent and child nodes (thus their p_id is not null and they appear in the p_id column at least once). Leaf nodes are those absent from the p_id column.

My code works by categorizing the root node first, then inner nodes and finally leaves. These are all connected by UNIONs. My submission is incorrect for a particular test case because the last of the three subqueries for leaves returns nothing, so I've isolated that portion of code below the second UNION. The full code is shown here:

select id, 'Root'
from tree
where p_id is null

union

select distinct p_id, 'Inner'
from tree
where p_id is not null
  and p_id not in (select id from tree where p_id is null)

union

select id, 'Leaf'
from tree
where p_id is not null
  and id not in (select distinct(p_id) from tree)

The test case with output and expected output are below. Recall this is output from just the bottom third of the code above (starting with "select id, 'Leaf'" below the 2nd UNION statement). The output returns nothing, whereas it should return all leaf nodes.

When I remove the last condition "and id not in (select distinct(p_id) from tree)", which just leaves select id from tree where p_id is not null, it correctly returns all inner and leaf nodes together, so the problem is with the "and id not in (...)" condition.

Can anyone identify why this isn't working? This seems like very basic syntax to me and I cannot figure out why this does not work properly.

Test case output from the leaf node subquery:

enter image description here

Solution

  • I believe I figured out the issue. For some reason the "and id not in" statement only works when the following subquery does not contain null values. Therefore the last part of the original query includes a where condition to exclude nulls:

    and id not in
(
    select distinct(p_id) from tree **where p_id is not null**
)