Binary Tree Nodes

---

Link

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.

풀이

---

IN

열명 IN (집합)

• WHERE구의 OR 조건과 동일
• 집합 안에 값이 포함되어 있으면 참

• P가 NULL이면 Root
• N이 P에 있으면 Inner
• 나머지는 Leaf

CASE
	WHEN P IS NULL THEN 'Root'
	WHEN N IN (SELECT DISTINCT P FROM bst) THEN 'Inner'
	ELSE 'Leaf'
END

---

틀렸던 풀이

• P가 NULL이면 Root
• N이 P에 없으면 Leaf
• 나머지는 Inner

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

🔍 왜 틀렸을까?

NOT IN의 경우, 집합 안에 NULL이 있으면 설령 왼쪽 값이 집합 안에 포함되어 있지 않아도 참을 반환하지 않는다. 그 결과는 Unknown 이 된다.

SELECT N
FROM BST
WHERE N NOT IN (SELECT DISTINCT P from BST) 

Sample Input을 기준으로,
위 쿼리를 실행하면 N을 하나하나씩 2, 5, 8, Null과 비교해서 N!=2, N!=5, N!=8, N!=null, 이 4가지 연산 모두 True 값을 반환하는 경우에만 N이 출력됩니다.

그런데 null과의 비교연산에서는 True도 False도 아닌 Unknown 값을 반환하게 되므로, 어떤 N도 N!=null 을 통과하지 못합니다.

WHERE P IS NOT NULL

조건을 넣어주면 N과 null의 비교연산을 하지 않아도 되니 N!=2, N!=5, N!=8, 이렇게 3가지 조건을 모두 만족하는 값들이 출력됩니다. (답변 : 데이터리안)

My Answer

---

SELECT N
    , CASE
          WHEN P IS NULL THEN 'Root'
          WHEN N IN (SELECT DISTINCT P FROM bst) THEN 'Inner'
          ELSE 'Leaf'
      END
FROM bst
ORDER BY N