[SQL] SQL로 이진트리 탐색하기(HackerRank - Binary Tree Nodes 문제)

🔊 본 포스팅에서 사용되는 테이블의 자료와 출처는 HackerRank 임을 밝힙니다. 더 다양한 SQL 문제를 풀어보시려면HackerRank 사이트를 방문해 보세요!

 

HackerRank 사이트

 

이번 포스팅에서는 SQL로 이진트리를 탐색하는 문제를 풀어보려 한다. 문제 원본은 여기를 클릭해 확인하자.

 

우선은 이진트리(Binary Tree)는 다음과 같은 특성을 갖고 있다. $Leaf$ 노드를 제외하고 $Root$ 노드를 포함한 모든 부모(Parent) 노드는 자신의 노드값 기준으로 왼쪽은 무조건 작은 값, 오른쪽은 무조건 큰 값이 존재하는 트리 구조라고 할 수 있다. 단, 부모 노드에 자식 노드가 하나만 존재하는 것이 가능하다. 텍스트로 이해하기 쉽지 않을 수도 있기에 이진트리의 구조를 사진으로 가져와 보았다.

 

이진트리(출처 : Wikipedia)

 

이제 이진트리가 무엇인지도 알았으니 문제에서 요구하는 사항을 살펴보자.

 

Write a query to find the node type ofBinary Treeordered by the value of the node. Output one of the following for each node(각 노드가 어떤 노드를 가리키는지 문자열로 명시하고 출력 결과를 노드의 값 기준으로 오름차순하여 정렬해라. 이 때 루트노드라면 $Root$를, 가장 마지막의 노드들이라면 $Leaf$를, $Root$노드를 제외한 나머지 부모노드들은 $Inner$를 출력해라.)

해당 문제를 해결하기 위해 사용한 아이디어들은 다음과 같다.

 

• 특정 조건에 맞는 값에 따라 문자열을 출력해주어야 하므로 CASE WHEN 또는 IF 문을 사용할 수 있을 것 이다.
• 우선 문제 원본에서 예시 I/O으로 주어진 데이터들로 이진트리 구조를 만들어 그려보자.
• N은 자식노드 P는 부모노드를 가리키므로 이 두개가 동일하도록 하면서 INNER JOIN을 시켜보자.

우선 문제에서 주어진 데이터들을 N = P 를 기준으로 INNER JOIN을 시키면 다음의 테이블과 같아진다.

 

$b_1$		$b_2$
N(자식노드)	P(부모노드)	N(자식노드)	P(부모노드)
1	2	2	5
3	2	2	5
6	8	8	5
9	8	8	5
2	5	5	Null
8	5	5	Null

 

위 테이블은 하단의 이진트리 구조를 반영한 테이블이다.

 

문제에서 주어진 이진트리 구조

 

 

위 그림과 INNER JOIN 시킨 테이블을 비교해보면 $b_2$ 테이블의 P값이 NULL일 때 $b_2$의 N값을 보면 $Root$노드인 것을 볼 수 있다.

 

그리고 $b_2$ 테이블의 P값이 NULL이 아닐 때 $b_2$의 N값들을 보면 모두 $Inner$노드인 것을 알 수 있다. 그리고 이 두 종류 노드에 속한 값들을 제외한 나머지 값이 들어있는 노드들은 $Leaf$노드임을 자동으로 판단할 수 있다.

 

필자는 조건문에 SELECT 서브쿼리문을 넣으려고 해서 가시적으로 보기에 IF 구문보다는 CASE WHEN 구문을 사용하기로 결정했다. 따라서 정답 SQL 구문은 다음과 같다.

 

SELECT N,
       CASE WHEN N IN (SELECT DISTINCT b2.N
                       FROM BST b1
                        INNER JOIN BST b2 ON b1.P = b2.N
                       WHERE b2.P IS NULL) THEN 'Root'
            WHEN N IN (SELECT DISTINCT b2.N
                       FROM BST b1
                        INNER JOIN BST b2 ON b1.P = b2.N
                       WHERE b2.P IS NOT NULL) THEN 'Inner'
            ELSE 'Leaf'
            END
FROM BST
ORDER BY N

 

마지막에 노드에 있는 값들을 기준으로 오름차순 정렬해주기로 했으므로 N 칼럼을 기준으로 ORDER BY 시켜주자.

 

이렇게 마지막 이진트리 탐색 문제까지 HackerRank의 Medium 난이도 문제를 모두 해치웠다!🔥