HackerRank SQL - 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

The Binary Tree below illustrates the sample:

 

 

Problem

Root : 노드가 루트이면

Leaf : 노드가 잎이면

Inner : 노드가 내부이면 

를 기준으로 이진 트리의 노드 유형을 찾는 쿼리 작성

---

Answer1

SELECT RESULT.N, (CASE WHEN RESULT.T = 'ROOT' THEN 'Root'
                      WHEN RESULT.C = 0 THEN 'Leaf'
                      ELSE 'Inner' END) as result
FROM (
SELECT B.N
       , IF(ISNULL(B.P), 'ROOT', 'NORMAL') T
       ,(SELECT COUNT(TEMP.P) FROM BST TEMP WHERE TEMP.P = B.N) C
  FROM BST B
GROUP BY B.N, T
ORDER BY B.N
) RESULT

B.P 중 NULL 있는 B.N값은 Root로 바꿔주고,

P의 개수를 세어 0이면 Leaf, 2면 Innner가 되는 조건으로 작성했다.

 

---

How to solve

오늘 데이터 분석가 코딩테스트에서도 비슷한 게 나왔다. 

SELECT B.N
       , IF(ISNULL(B.P), 'ROOT', 'NORMAL') T
       ,(SELECT COUNT(TEMP.P) FROM BST TEMP WHERE TEMP.P = B.N) C
  FROM BST B
GROUP BY B.N, T
ORDER BY B.N

일단 처음에 시도한 것은 NULL값이 있는 Root 노드를 따로 빼두고 싶었다.

저걸 같은 컬럼에서 처리하고 싶어서 이것 저것 해봤는데 도저히 답을 못찾겠다.

 

결국 또 쉬운 길인 서브쿼리 사용....

 

이후에는 CASE WHEN 구문으로 쿼리를 완성하면 쉽다.

 

 

23-07-21 추가 내용

오늘부터 중급문제를 다시 풀어볼텐데 이전에 한 걸 보니, 지금이랑 전혀 다르게 접근했었다.

근데 엄청 어렵게 풀었었는데 왜 저렇게 풀었는지 지금은 이해가 안간다.😂

 

아무튼 이번에는 select문에 case when 구문을 두고 풀었다.

성능은 더 안좋을 지언정, 휠씬 직관적이라서 이게 더 낫겠다는 생각이 들었다.

select b.N, (case when b.p is null then 'Root'
                  when(select count(*) from BST b2 where b2.P = b.N) = 0 then 'Leaf'    
                  when(select count(*) from BST b2 where b2.P = b.N) > 0 then 'Inner'                                                 end) 
from BST b
order by N asc;