문제
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
Plain Text
복사
정답
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;
SQL
복사
풀이
•
계층형 질의 문제인 줄 알았으나, 단순히 서브쿼리만 잘 이용해도 풀리는 문제이다.
•
조건을 보면, Parent가 없으면 Root이고 Inner의 경우 그 값이 Parent에 존재하기만 하면 된다(Root 제외). 따라서 CASE WHEN 을 사용하여 서브쿼리 문제로 풀면 된다.
•
Root인 경우 P가 Null이어야 하므로
CASE WHEN P IS NULL THEN 'Root'
SQL
복사
•
Inner인 경우 P를 Distinct하게 구한다음 N이 그 리스트에 속하는 지를 확인하자. 이때 앞에서 이미 루트를 구했기 때문에 루트가 Inner로 출력될 일은 없다.
WHEN N IN (SELECT DISTINCT P FROM BST) THEN 'Inner'
SQL
복사
•
그리고 나머지는 Leaf다.
ELSE 'Leaf'
SQL
복사