[MySQL/HackerRank] Binary Tree Nodes 문제풀이

 

https://www.hackerrank.com/challenges/binary-search-tree-1/problem

 

해당 문제는 이진 트리에 관한 문제이다. 각 노드(Root, Leaf, Inner)의 타입을 리턴하는 문제.

 

BST table에 각 컬럼을 살펴보면,

N은 각 노드의 값을 나타내고, P는 N의 부모의 값을 나타낸다.

 

우선 각 타입에 대해 생각을 해보면, 

Root는 가장 최상위 노드이므로, P가 NULL일 것이고, 

Leaf는 자식이 없는 노드이다. 즉, 자기 자신을 P값으로 가지는 노드가 없다는 것이다.

Inner는 Root도, Leaf도 아닌 노드이다.

 

이제 이것을 sql로 나타내면

아래와 같다.

 

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

NOT IN 안에 서브 쿼리는 BST table에서 부모의 값을 모두 가져온다.

그런데 여기서 주의할 점은, NOT IN 구문에는 null이 들어오면 아무 row도 출력하지 않는다.

물론 여기서는 루트를 제외해야하기 때문에 Null을 제거하는 이유도 있지만, NOT IN , IN 구문에서 null이 연산되지 않는다는 것을 기억해야한다.

 

 

문제를 풀어보고 나니, IN 보다 EXISTS가 더 성능에 좋다는 게 생각이 나서 다시 EXISTS 구문을 사용하여 풀어보았다.

 

select N, 
      (case when p is null then 'Root' 
      when Exists (select P from BST T where B.N = T.P) then 'Inner' else 'Leaf' end)
from BST B
order by N

 

EXISTS와 IN에 대해 간단히 설명을 하면,

 

EXISTS : 메인 쿼리의 결과값을 서브 쿼리에 대입하여 조건 비교 후 결과를 출력한다. ( 메인쿼리 -> EXISTS 쿼리 )

IN : 서브 쿼리의 결과값을 메인 쿼리에 대입하여 조건 비교 후 결과를 출력한다. ( IN쿼리 -> 메인 쿼리 )

 

EXISTS는 해당 서브쿼리에 대한 ROW가 존재하는지만 체크하고 더이상 수행하지 않는다.

하지만, IN은 해당 데이터가 모두 존재하는지 체크하기때문에 IN쿼리의 row가 많을수록 EXISTS보다 성능이 떨어지게 된다.