SQL Server中NOT IN运算符失效：二叉树节点查询返回NULL原因

最近在刷HackerRank的二叉树相关SQL题，题目要求很明确：给定一张包含N（节点值）和P（父节点值）两列的BST表，编写查询语句按节点值排序，同时判断每个节点的类型——是Root（根节点）、Leaf（叶子节点）还是Inner（内部节点）。

我最后用这条语句成功解决了问题：

select n, case when p is null then 'Root' when p is not null and (n in (select p from BST)) then 'Inner' else 'Leaf' end from BST order by n

不过之前踩了个坑，写的另一条语句总是出问题：根节点和内部节点能正常返回类型，但叶子节点全是NULL。那条有问题的语句是这样的：

select n, case when p is null then 'Root' when p is not null and (n in (select p from BST)) then 'Inner' when p is not null and (n not in (select p from BST)) then 'Leaf' end from BST order by n

后来才搞明白问题出在**NOT IN和NULL的交互逻辑**上！

因为我们的BST表中，父节点列P肯定存在NULL值（根节点的父节点就是NULL），当执行子查询select p from BST时，结果集合里会包含这个NULL。而SQL里的NOT IN在处理包含NULL的集合时，逻辑很特殊：如果n NOT IN (包含NULL的集合)，这个表达式的结果既不是TRUE也不是FALSE，而是UNKNOWN。

而CASE语句只会匹配条件为TRUE的分支，UNKNOWN的条件不会被任何WHEN分支捕获，所以叶子节点的判断分支永远不会触发，最终返回NULL。

而成功的那条语句用ELSE 'Leaf'兜底，不管前面的条件是FALSE还是UNKNOWN，都会进入这个分支，自然就正确返回了叶子节点的类型。

内容的提问来源于stack exchange，提问作者Shahzad Ahamad