[HackerRank] Binary Tree Nodes

Binary Tree Nodes | HackerRank

---

문제

 

문제 접근 방식

p가 n의 부모라는 점을 충분히 인지하고 문제에 접근해야 한다.

- 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 WHERE p IS NOT NULL) THEN "Leaf" 
            ELSE "Inner" 
        END AS 'node_type' 
FROM bst 
ORDER BY n ASC
;

 

위의 조건들로 case when 구문을 활용하여 쿼리를 짜면 완성.

 

 

BST 테이블의 구조를 잘 파악한다면 금방 풀 수 있는 문제이다.

그런데 나는 너무 어렵게 생각을 했고 셀프 조인을 반드시 해야 한다는 생각을 했다.

 

쿼리로 정답을 도출하긴 했으나 내 쿼리는 트리 깊이를 한정 지어서 작성한 것이라

만약 트리 깊이가 다른 경우에는 내가 작성한 쿼리로 조회했을 때에는 오류 응답이 나오게 될 가능성이 크다.

 

SELECT DISTINCT a1
     , CASE 
           WHEN a2 IS NULL AND a3 IS NULL AND a4 IS NULL THEN 'Leaf'
           WHEN a2 IS NOT NULL AND a3 IS NOT NULL AND a4 IS NOT NULL THEN 'Root' 
           ELSE 'Inner' 
       END 
FROM (
    SELECT a1.n a1, a2.n a2, a3.n a3, a4.n a4
    FROM BST a1
    LEFT JOIN BST a2 ON a1.n = a2.p
    LEFT JOIN BST a3 ON a2.n = a3.p
    LEFT JOIN BST a4 ON a3.n = a4.p
);

 

트리 깊이를 직접 정의하는 쿼리는 잘못된 쿼리임을 인지하고

이럴 경우, 다른 방법이 있다는 사실을 항상 기억하기!