[해커랭크] MySQL - Binary Tree Nodes

 

 

 

---

 

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.

출처 : 해커랭크

BST라는 테이블이 있고 N과 P 두 개의 컬럼을 포함하고 있습니다. P는 N 컬럼의 상위(부모)의 속성을 가지는 컬럼을 의미합니다.

 

출처 : 해커랭크

위의 예시 그림과 같이 숫자 5는 Root라는 속성을 가지고 있고 1, 3, 6, 9는 Leaf라는 속성을 가지게 됩니다. 중간에 있는 속성들은 Inner라는 속성을 가지게 됩니다.

 

출처 : 해커랭크

예시 테이블을 통해서 CASE 구문을 활용해서 문제를 풀어보면 될 것 같습니다.

 

첫 번째로는 p 컬럼에 null 값을 가지고 있으면  Root 속성을 부여하면 됩니다.

select n
     , case
        when p is null then "Root"
       end 
from bst
order by 1

두 번째로는 p 컬럼에 같은 값이 2개가 있다면 Inner 속성을 가지게 됩니다. 예시에서는 숫자 5도 p 컬럼에 2개 이상 포함되어 있지만 첫 번째 조건에서 이미 Root 속성을 부여하였기 때문에 숫자 5에 대해서는 적용되지 않습니다.

select n
     , case
        when p is null then "Root"
        when n in (select p from bst group by p having count(*) >= 2) then "Inner"
        else "Leaf"
       end 
from bst
order by 1

두 번째 When 구문에서 GROUP BY 및 HAVING을 활용하여 "Inner" 값을 부여해줍니다. 그리고 이외의 값은 else를 통해 "Leaf" 값을 부여해주면 됩니다.

 

처음에는 셀프 조인을 활용하여 문제를 풀어보려고 했으나 이진 트리가 길어지면 셀프 조인을 하는데 끝이 없었고 위와 같은 방식으로 풀면 어떠한 예시에서도 문제를 풀 수 있었습니다.

 

---