해커랭크 - BST 문제 풀이

오랜만에 sql 코테를 풀어보았다. 해커랭크는 영어라 한국어로 번역해서 풀어야 한다.

Binary Tree Nodes | HackerRank

 

 

문제요약

• 입력은 테이블 BST(N, P) — 각 행이 트리의 노드 N 과 그 부모 P
• 각 노드 N 에 대해 그 노드가 트리에서 Root, Inner, 또는 Leaf 중 어느 타입인지 판별
• Root: 부모가 없는 노드 (즉, P IS NULL) 
• Inner: 부모가 있고, 동시에 자식이 있는 노드 (즉, 다른 노드가 자신의 자식으로 이 노드를 부모로 참조)
• Leaf: 자식이 없는 노드 (즉, 아무도 이 노드를 부모로 가리키지 않음)
• 결과는 N 오름차순 정렬해서 출력

 

문제풀이

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 1;

• P IS NULL → 부모가 없으므로 Root
• N IN (SELECT P FROM BST) → 이 노드가 다른 노드의 부모라면 자식이 있다는 의미 → Inner
• 그렇지 않으면 자식 없는 노드 → Leaf