[코딩테스트] 해커랭크 Hackerrank SQL Binary Tree Nodes 문제풀이

SQL 코딩테스트 준비를 위해 해커랭크 문제풀이를 해보려고 합니다. 서버는 MySQL을 기준으로 설정하였으며, 문제의 핵심은 sql로 조건문 case when 사용하고, where절에 not in을 이해하는 것입니다. SQL 코딩 능력을 키우고자 하는 분들에게 도움이 될 수 있도록 문제 해결에 필요한 사고 과정과 코드 설명을 상세히 다루었습니다.

 

 

문제 : Binary Tree Nodes (hackkerrank sql, mysql) 

난이도 : Medium

서버 : MySQL

문제 의도 : 조건문 사용, WHERE절에서 NOT IN 응용할 수 있는지? 

테이블 이름 : BST

 

https://www.hackerrank.com/challenges/binary-search-tree-1/problem?isFullScreen=true

Binary Tree Nodes | HackerRank

 

 

 

문제 요약 : 이진 트리 문제로, 자식노드와 부모노드 (n,p) 데이터를 통해 해당 노드가  root, leaf, inner node 3가지 노드 중 어느 노드인지 입력하는 문제 

 

input sample

 

output sample

 

 

정답 SQL 코드 :

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
FROM BST
ORDER BY N

 

 

 

풀이 과정 : 

(나의 풀이과정 사고정리) 

 

1. 부모 노드가 없으면 root node 
2. 자식 노드가 없으면 leaf node 
3. root, leaf node 둘 다 해당되지 않는 다면 inner node 

 

 

일단, 조건문을 생각했는데 다음과 같이 작성했다. 

SELECT n, 
CASE WHEN p IS NULL THEN 'root' 
WHEN n not in (SELECT DISTINCT p FROM BST) 
     THEN 'leaf' 
     ELSE 'inner' end 
FROM BST
ORDER BY N

 

그러나, Wrong answer 이었는데, 

 

❗️ 주의사항 ❗️

다음에서 놓친 부분 2가지

[1] 열이름과 해당되는 데이터에서 대소문자 구별하기! 

n,p -> N, P / root -> Root 등 대소문자를 구별하지 않아 문제점이 발생했었다. 

 

[2] NOT IN은 NULL값이 연산되지 않아 잘못 계산된다는 오류 발생 
NOT IN 에서 해당 P 데이터가 NULL인 경우가 있을 수 있으나, 그 경우는 제외시켜주는 조건을 추가해야한다. 

만약 Where P IS NOT NULL 인 조건을 추가해주지 않는다면 

아래와 같이 데이터가 나온다. 

 

 

 

 

따라서, 다음과 같은 코드를 실행하면 정답!

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'
FROM BST
ORDER BY N

 

 

+ 추가 

 

또 다른 SQL 풀이법

 

또 다른 방법으로 풀기 위해 현재 테이블을 복제한 자식, 부모 테이블을 만들어 

LEFT JOIN을 통해 비교할 수 있는 방법이 있다는 것을 알게 되었다. 

 

 

흠..그런데 이 풀이법은 100% 이해하지 못했지만..ㅎㅎ 

 

BST = NOW 테이블 (현재 테이블로 보고) 

위 아래로 

 

PARENT의 P, N 

BST의 P, N

CHILD의 P, N

LEFT JOIN을 통해 자식, 부모 노드의 관계를 정확히 확인하고, 

조건 : BST.P 가 NULL이면 즉, 부모 노드가 없으면 Root node이고 , CHILD.P 가 NULL이면 즉, 자식 노드가 없으면 Leaf node임을 

작성한다. 

 

 

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

 

이미지 출처 : bell.log 블로그