오늘도 데이터분석

Binary Tree Nodes 문제 바로 가기

문제

문제 정리

- BST 테이블에 노드 값이 담긴 N과 노드의 부모값이 담긴 P  두 가지 속성이 있음.
- 이진트리의 각 노드의 노드타입을 결과로 나타내는 쿼리입력.
   (1)노드가 루트노드면 Root (최상위 노드, 부모가 없는 노드)
   (2)노드가 리프노트면 Leaf (자식이 없는 노드)
   (3)노드가 이너노드면 Inner(루트도, 잎 노드도 아닌 노드)
- N 내림차순 정렬

You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

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.

Sample Input

Sample Output

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

Explanation

The Binary Tree below illustrates the sample:

풀이

CASE 문 만들기 

* CASE문은 조건문 여러개 가능
EX)  CASE (조건문1)WHEN ~ THEN ~ (조건문2)WHEN ~ THEN ~ (조건문3)ELSE ~  END

1. 노드가 루트노드면 Root (최상위 노드, 부모가 없는 노드)
  
 P가NULL이면 부모가 없는 최상위 노트
-->  CASE WHEN P IS NULL THEN 'Root'

2.노드가 리프노트면 Leaf (자식이 없는 노드)

(1) 자식이 없다 => 부모가 아니다 => N값(부모)이 P에 없다 
N NOT IN P

(2) 속성P의 속성값을 범위로 나타내려면 서브쿼리로 표시
SELECT P FROM BST 

(3) P 속성값 중 NULL이 있는 경우 NOT IN을 하면 아무 row도 선택하지 않음 
ex) N not in (2,, null) => N <> 2 AND N <> NULL 의미,
그러나 NULL은 IS NOT NULL로 찾을 수 있기 때문에 N not in (2,, null) 식은 항상 FALSE를 반환하게 됨 
P의 NULL값을 제거하는 범위 지정

--> WHEN N NOT IN (SELECT P FROM BST WHERE P IS NOT NULL) THEN 'Leaf'

3. 노드가 이너노드면 Inner(루트도, 잎 노드도 아닌 노드)

1, 2 조건문이 아니면 이너노드 
--> ELSE 'Inner'

중요 포인트 

1. CASE 문 안에 서브쿼리

2. NOT IN 의 '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) AS type
FROM BST
ORDER BY N