문제 링크

문제 조건

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.

테이블의 데이터를 보고 각각의 노드가 어디에 위치해 있는지 정보를 나타내어야 하는 문제이다.

문제 해결

n, p 의 값을 보고

if) n 의 값을 가지고 있는 p가 없다(null) → leaf

if) p가 없다(null) → root

else) Inner

같은 BST 테이블을 3개를 이용해서

NOW, CHILD, PARENT join 을 하고

(CHILD 가 Null 인것들을 검증해야 하기 때문에 LEFT JOIN을 해야함!!)

CASE 문을 통해 검증하면 될것같다.

그리고 마지막으로 NOW.N 값으로 정렬해주면 된다.

테스트 케이스로 테이블 만들어보기

NOW.N	NOW.P	CHILD.N	CHILD.P	PARENT.N	PARENT.P	result
1	2	null	null	2	5	Leaf
3	2	null	null	2	5	Leaf
6	8	null	null	8	5	Leaf
9	8	null	null	8	5	Leaf
2	5	3	2	5	null	Inner
8	5	9	8	5	null	Inner
5	null	2	5	null	null	Root
5	null	8	5	null	null	Root

SQL 로 구현

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

정답!!