[HackerRank/SQL] Binary Tree Nodes

[HackerRank/SQL] Binary Tree Nodes

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

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

from http://developearl99.tistory.com/150 by ccl(A) rewrite - 2021-11-07 17:26:39