MySQL >Binary Tree Nodes

---

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:

이진트리에 대한 이해가 필요
참고 페이지
https://cinux.tistory.com/8
https://techblog-history-younghunjo1.tistory.com/175

My Answer

---

#0.노드 정의하기

Root: 가장 상위의 노드
Leaf: 가장마지막 노드
Inner: Root와 Leaf가 아닌 노드

즉, 주어진 이미지를 다시 보면

Root: 가장 상위의 노드 (5)
Leaf: 가장 마지막 노드 (1,3,8,9)
Inner: Root와 Leaf가 아닌 노드 (2, 8)

#1 N은 자식노드 P는 부모노드를 가리키므로 이 두개가 동일하도록 하면서 INNER JOIN

SELECT *
FROM BST b1 JOIN BST b2 ON b1.p = b2.n

-> b2.P가 NULL이면 b1.N은 Root
-> b2.p가 NOT NULL이면 b1.N은 Leaf
-> 나머지는 INNER

-- CASE문에 IN 사용
-- CASE절은 위에서부터 순차적으로 출력! Root > Inner > Leaf순으로 출력
SELECT N, CASE WHEN N IN (SELECT DISTINCT b2.n
                     FROM BST b1 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 JOIN BST b2 ON b1.p = b2.n
                     WHERE b2.p is NOT null) THEN 'Inner'
               ELSE 'Leaf' END
FROM BST
ORDER BY N ;

참고
https://haloaround.tistory.com/212