[SQL]해커랭크 Binary Tree Nodes

LEFT JOIN과 서브쿼리를 사용한 2가지 풀이가 가능합니다.

서브쿼리를 사용한 코드부터 살펴보겠습니다.

 

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;

4번째 줄의 WHERE문을 입력하지 않으면 원하는 대로 코드가 출력되지 않습니다.

이 부분을 이해하느라 상당히 많은 시간이 소요됐는데 원인은 컬럼 P에 있는 NULL 때문입니다.

NULL 값을 다룰 때는 항상 주의해야 할 것 같습니다.

IS NOT NULL 조건이 없으면 Leaf 노드여야 할 노드들이 모두 Inner 노드로 분류됩니다.

 

SELECT std.N
     , CASE
           WHEN std.P IS NULL THEN 'Root'
           WHEN child.P IS NULL THEN 'Leaf'
           ELSE 'Inner'
       END AS node_type
FROM BST AS std
    LEFT JOIN BST AS child ON std.N = child.P
ORDER BY std.N;

다음은 LEFT JOIN을 사용한 풀이입니다.

조인의 기준(ON)을 어떻게 설정하느냐에 따라 조인 결과 테이블의 형태가 달라집니다.

중요한 것은 트리의 레벨이 4 이상인 경우입니다.

총 레벨이 4인 경우를 가정하면 Root/ Inner, Inner/ Leaf 층으로 분류됩니다.

위 코드는 Inner와 Leaf 노드들을 적절하게 분류합니다.

 

SELECT std.N
     , CASE
           WHEN std.P IS NULL THEN 'Root'
           WHEN parent.P IS NULL THEN 'Inner'
           ELSE 'Leaf'
       END AS node_type
FROM BST AS std
    LEFT JOIN BST AS parent ON std.P = parent.N
ORDER BY std.N;

하지만 위 코드는 다릅니다.

Inner와 Leaf 노드를 분류하는 깔끔한 기준을 제시하지 못합니다.