[해커랭크(HackerRank)] Binary Tree Nodes (MySQL)

문제

1. 2진 트리 문제. N은 이진 트리의 노드 값, P는 N의 상위 항목
2. Root → 최상위 노드인 경우, 부모가 없는 노드 → 5가 최상위 노드
3. Leaf → 최하위 노드인 경우, 자식이 없음 → 1, 3, 6, 9 → n이 p의 범위에 포함되지 않는 것들
4. Inner → root도 leaf도 아닌 경우 → 2, 8
5. 각 조건에 해당하는 노드 출력

코드

1. subquery

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

• 각 node에 대해서 parent의 case 따라 node type이 결정
• parent is null 일 경우 Root
• parent 리스트 안에 N이 없을 경우 Leaf
• 나머지 Inner

2. join

select distinct a.n
     , case when a.p is null then 'Root' 
            when b.p is null then 'Leaf'
            else 'Inner' end
from bst a
     left join bst b 
     on a.n = b.p 
order by a.n

• n이 p에 포함되지 않을 때 leaf가 되는데 그걸 검사하기 위해서는 left join이 필요하다.
• 조건에 만족하지 않을 때 포함되지 않을 때 null이 표시 되기 때문에 그걸 이용해 leaf를 출력할 수 있을 것 같았다.
• 처음에 inner join을 해봤으나 불가능했음

inner join

left join

• left join을 했을 때 a.n이 b.p에 포함되지 않으면 null이 출력된다
• 그렇다면 a.p가 null일 때 root가 되고 b.n이 null이면 left 그 나머지일 때는 Inner가 된다

출처

Binary Tree Nodes | HackerRank