[SQL] Binary Tree Nodes

✅ 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

---

💻 풀이

SELECT
    B1.N,
    (CASE
        WHEN B1.P IS NULL THEN "Root"
        WHEN B3.P IS NOT NULL THEN "Leaf"
        ELSE "Inner"
    END) AS result
FROM BST AS B1 LEFT OUTER JOIN BST AS B2 ON B1.P = B2.N
    LEFT OUTER JOIN BST AS B3 ON B2.P = B3.N
ORDER BY B1.N ASC;

---

💡 Idea

SELF JOIN 방법을 이용했다. 하지만 MySQL에서는 해당 함수를 지원하지 않으므로 LEFT OUTER JOIN 함수를 중첩하여 풀었다.

예시를 들자면 부하 직원들을 담당하는 상사가 있다고 생각하면 된다.

부하	상사	부하	상사
1	2	2	4

부하 1의 상사는 2이고, 2의 상사는 4이다.
만약 4가 직장 내의 제일 높은 직위를 가졌다고 가정하면, 4의 상사는 존재하지 않기 때문에 NULL이 입력된다.

따라서 위의 원리를 이용하여 풀었다.

---