HackerRank Mysql 문제풀이 - Binary Tree Nodes

HackerRank Mysql - Binary Tree Nodes 

사전지식.

- Sub Query 서브 쿼리
- Control Flow Function 제어문
- NULL 체크

 

1. 문제 해석

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.

Output
N node type
1    Leaf
2    Inner
3    Leaf
5    Root
6    Leaf
8    Inner
9    Leaf

 

각 node 에 대해서 P parent 의 case 따라서 node type 이 결정
nodeType case 분기로직 을 잘 짜는 것이 포인트! + SubQuery 를 짜는 법!

 

2. 쿼리문 구조 결정 

- node type 결정하는 값 1개를 반환하는 서브쿼리 하나!
BST 테이블에서 한개의 행씩 읽으면서 N과 nodeType 결과를 반환한다.
(그래서 subquery 안에 따로 from 을 넣지 않는다! select 도 생략해도 된다.)

select N, (... 
    ) as nodeType
from BST
order by N;

 

node type 을 구하는 로직

- parent is null --> Root
- parent 리스트 안에 없으면 --> Leaf 
- 나머지 --> Inner

오늘의 발견! IN 절은 Null 을 섬세히 다뤄야 한다. 그래서 not null 로 조건 걸어줬다.
(parent list 를 Integer list 로 바꿔서 테스트해보고서야, null 빠져야 제대로 동작한다는 걸 알아냈다.)

To comply with the SQL standard, IN() returns NULL 
- not only if the expression on the left hand side is NULL,
- but also if no match is found in the list
- one of the expressions in the list is NULL. 
ref. Comparison Functions and Operators > IN

case when P is null then 'Root'
	when N not in (select distinct P from BST where P is not null) then 'Leaf'
    else 'Inner' end

 

3. 최종 쿼리

select N, (
	case when P is null then 'Root'
   	 when N not in (select distinct P from BST where P is not null) then 'Leaf'
  	  else 'Inner' end
    ) as nodeType
from BST
order by N;

 

 

PS. 서브쿼리 대신 Integer 리스트 넣어보고 깨달았다. 오늘의 띵포인트!