[HackerRank] Oracle - Binary Tree Nodes

혼자 풀었는가 ? X

---

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.

Sample Input

Sample Output

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

Explanation

The Binary Tree below illustrates the sample:

 

간단하게 말하면, 본인 노드를 기준으로,  자식과 부모의 유무를 따져

부모가 없으면 Root, 자식이 없으면 Leaf, 그 외의 경우 Inner로 분리하면 되는 문제이다. 

JOIN을 사용하여  한번에 조건을 확인할 수 있다.

SELECT NOW.N, NOW.P, CHILD.N, CHILD.P
FROM BST NOW
    LEFT JOIN BST CHILD ON NOW.N = CHILD.P;

해당 구문을 통해 NOW의 부모 유무, NOW 의 자식 유무를 확인할 수 있다.

필요한 데이터만 셀렉 후, CASE 문으로 필요한 정보를 마저 빼고

중복 제거 + 오름차순을 진행해주면 된다. 

SELECT DISTINCT NOW.N, 
    CASE
        WHEN NOW.P IS NULL THEN 'Root'
        WHEN CHILD.N IS NULL THEN 'Leaf'
        ELSE 'Inner'
    END AS Node
FROM BST NOW
    LEFT JOIN BST CHILD ON NOW.N = CHILD.P
ORDER BY NOW.N;

LEFT 조인인 이유는, 누락되는 노드가 존재하면 안되기 때문이다!