[SQL] 해커랭크 HackerRank 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.

 

해석

주어진 테이블 BST는 이진 트리(Binary Tree)의 정보를 담고 있으며, 두 개의 컬럼이 있다.

컬럼설명

N	노드의 값
P	부모 노드의 값 (루트 노드는 부모가 없음)

 

출력 조건

각 노드에 대해 다음 중 하나를 출력해야 한다.

1. Root (루트 노드)
   • P IS NULL이면 루트 노드이다. (즉, 부모가 없는 노드)
2. Leaf (리프 노드)
   • 해당 노드(N)가 다른 노드의 P 값에 존재하지 않으면 리프 노드이다.
   • 즉, 자식이 없는 노드이다.
3. Inner (내부 노드)
   • Root도 아니고, Leaf도 아닌 노드이다.
   • 즉, 부모도 있고 자식도 있는 노드이다.

 

정답

 

SELECT 
    N, 
    CASE 
        WHEN P IS NULL THEN 'Root'  
        WHEN N IN (SELECT P FROM BST) THEN 'Inner'  
        ELSE 'Leaf'
    END AS tree
FROM BST
ORDER BY N;

배운 점

 

처음에는 이런 식으로 쿼리를 조인시켜서 이해했다.

a.n	a.p = b.n	b.p	구분
1	2	5	Leaf
3	2	5	Leaf
6	8	5	Leaf
9	8	5	Leaf
2	5	Null	Inner
8	5	Null	Inner
5	Null	Null	Root

 

초기 틀린 쿼리

select a.n, case when a.p is null and b.p is null then 'Root'
               when a.p is not null and b.p is null then 'Inner'
               else 'Leaf' end as tree
from bst a left join bst b on a.p = b.n
order by 1;

 

 

GPT 말로는 이런 오류가 있다는 데 

• JOIN은 a.p = b.n을 기준으로 동작하지만,
  우리가 판별해야 할 것은 a.n이 다른 노드의 부모인지 여부야.
• JOIN에서는 a.p만 고려하기 때문에, 노드가 자식을 가지는지 여부를 정확히 확인할 수 없다.
• b.n 값이 NULL인지 확인하는 것은 Inner와 Leaf를 구분하는 데 적절하지 않다.

아무래도 자식이 있는지에 대한 기준이 아니라 부모가 있는지에 대해 생각해봐야 하는 문제인거 같다.

 

 

•  처음에는 위와 같이 풀었는데 Root 조건 시 굳이 a.p랑 b.p조건 두개 안 걸어도 됨 -> 이거 수정해도 틀림
• b를 연결해서 이해할 게 아니라 a 하나로만으로도 서브쿼리와 함께 진행할 수 있다