[HackerRank/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.

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:

 

---

[풀이]

1. P가 NULL이면 부모 노드가 없다는 것을 의미하므로, P가 NULL인 노드가 루트 노드이다.

2. P가 NULL이 아니고, 모든 P 중에 N이 존재한다면, 해당 노드가 누군가의 부모 노드라는 것을 의미하고, 자식 노드가 있음을 의미한다. 즉 이때는 Inner 노드이다.

3. 위의 경우에 모두 해당되지 않는다면 리프 노드이다.

 

1~3을 CASE 문을 이용하여 아래 코드와 같이 구현한다.

N이 작은 순서대로 값을 조회할 것이므로 ORDER BY N을 작성한다.

 

[코드]

SELECT N,
CASE 
    WHEN P IS NULL 
    THEN 'Root'
    WHEN N IN (SELECT P FROM BST)
    THEN 'Inner'
    ELSE 'Leaf'
END
FROM BST
ORDER BY N