[SQL] HackerRank Binary Tree Nodes - CASE 구문 활용 (NOT IN이 안되는 이유)

해커랭크 SQL 문제 풀이: Binary Tree Nodes

문제링크: https://www.hackerrank.com/challenges/binary-search-tree-1/problem

Binary Tree Nodes | HackerRank

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.

 

이 문제는 N과 P라는 2개의 컬럼만을 가지고 있는 BST라는 테이블에서 각각의 노드(N)가 어떤 유형인지 구분하고 출력하는 문제입니다. 아래에 테이블 예시와 아웃풋 예시가 있습니다. Root는 P가 존재하지 않는 노드, Leaf는 본인이 마지막 노드인 경우(P의 역할을 하지 않으므로 P컬럼에 한 번도 등장하지 않는), 그 외 Parent와 Child를 모두 가지는 노드를 Inner라고 합니다.

-- BST 테이블                       -- 정답 아웃풋 예시
| N  | P  |                       | N  | node_type |
|----|----|                       |----|-----------|
| 1  | 2  |                       | 1  | Leaf      |
| 3  | 2  |                       | 2  | Inner     |
| 5  | 6  |                       | 3  | Leaf      |
| 7  | 6  |                       | 5  | Root      |
| 2  | 4  |                       | 6  | Leaf      |
| 6  | 4  |                       | 8  | Inner     |
| 4  | 15 |                       | 9  | Leaf      |

 

최종 결과는 N컬럼을 기준으로 정렬해서 출력해야 합니다.

 

Top Earners 정답: CASE 구문 활용

아래와 같이 정답을 작성할 수 있습니다.

SELECT
    N,
    (CASE
        WHEN P is null THEN "Root"
        WHEN N IN (SELECT P FROM BST) THEN "Inner"
        ELSE "Leaf"
    END) AS node_type
FROM BST
ORDER BY N

 

N과 함께 node_type을 출력했는데요. 각각의 노드(N)가 어떤 타입인지 구분하기 위해 CASE 구문을 사용했습니다. CASE 구문을 해석해 보면, P가 null이면 Root 노드, N이 P에도 있다면 Inner 노드, 둘 다 아닌 경우 Leaf 노드 값을 출력한다는 뜻입니다. 

 

여기서 주목할 점은 아래와 같이 CASE 구문에서 WHEN N IN (SELECT P FROM BST) THEN "Inner" 대신 WHEN N NOT IN (SELECT P FROM BST) THEN "Leaf"로 바꾸면 정답 처리가 되지 않는다는 뜻입니다.

SELECT
    N,
    (CASE
        WHEN P is null THEN "Root"
        WHEN N NOT IN (SELECT P FROM BST) THEN "Leaf" # Leaf 조건을 먼저 작성
        ELSE "Inner"
    END) AS node_type
FROM BST
ORDER BY N

 

순서만 바꿨을 뿐인데 왜 오답이 되는 것일까요?

 

왜 NOT IN은 안되는데 IN은 되는 것일까?

사실 DBMS의 세팅에 따라 제대로 출력되는 경우도 있지만 HackerRank에서는 오답으로 처리됩니다. 왜 그럴까요?

 

우선 원본 데이터를 다시 살펴볼 필요가 있습니다. BST 테이블에는 P컬럼에 null이 들어가 있는 데이터가 존재합니다. 바로 Parent 노드가 존재하지 않는 Root 노드죠. 그런데 여기서 N NOT IN (SELECT P FROM BST)라고 조건을 주면 N = NULL 인지 비교하게 되는 경우가 발생합니다. MySQL에서도 그렇고 NULL 값을 이렇게 같다, 같지 않다로 비교하는 것은 좋은 생각이 아닙니다. 경우에 따라 항상 거짓이거나 empty set을 반환하는 등 원치 않는 결과를 내놓기 때문이죠. 

 

따라서 여기서 NOT IN 이 안 되는 이유는 P값에 null이 존재하기 때문입니다. 그럼에도 NOT IN을 사용하고 싶다면 어떻게 해야 할까요?

SELECT
    N,
    (CASE
        WHEN P is null THEN "Root"
        WHEN N NOT IN (SELECT P FROM BST where P is not null) THEN "Leaf"
        ELSE "Inner"
    END) AS node_type
FROM BST
ORDER BY N

 

위와 같이 where절에서 P가 null인 행을 모두 필터링해 주면 됩니다. 이렇게 코드를 작성하면 IN을 사용할 때와 마찬가지로 제대로 된 결과를 출력하며 정답처리됩니다.

 

 

 

HackerRank 모든 문제 풀이 모음 바로가기

정확하고 꼼꼼하게 씁니다

모든 SQL 코딩테스트 문제 풀이 모음 바로가기

정확하고 꼼꼼하게 씁니다