[해커랭크 medium] Binary Tree Nodes(MySQL)

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

Binary Tree Nodes | HackerRank

 

흑... 열심히 고민했는데 생각보다 쉬웠던 문제...!

셀프조인해서 풀려고 했지만.... 그거슨 올바른 길이 아니었다 ㅠㅠ ㅋㅋㅋ

 

일단 정답 코드는 다음과 같다.

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

P는 N의 부모 노드이다.

그래서 P가 null이라는 건 N이 root 노드라는 것이고,

N의 value가 P에도 있다는 것은 N이 누군가의 부모 노드라는 것이기 때문에 inner node라는 뜻이 된다.

그리고 나머지 애들은 그냥 leaf 노드이다!

 

매우 간단하다..

나는 왜 이 생각을 못했을까ㅠㅠㅋㅋㅋㅋ

그래도 이렇게 풀다보면 나중엔 내 머리로 응용하는 날이 오겠지!!

 

 

 

내가 처음에 풀었던 방식처럼 join을 사용한 풀이도 있다.

select distinct a.n,
        case when b.p is null then "Leaf"
             when a.p is null then "Root"
             else "Inner"
        end
from bst a
left outer join bst b
on a.n = b.p
order by a.n

출처 : https://jogrammer.tistory.com/249?category=945862 

 

근데 이게 너무 헷갈린다 ㅠㅠ

일단 a.n과 b.p를 기준으로 left outer join을 한다.

 

그러면 아래와 같은 모양이 된다.

 

 

1) A.N에만 존재하고 B.P에는 존재하지 않으면(=B.P가 NULL이면) → Leaf (왜냐면 A.N이 부모 노드인 경우가 없으니까)

2) A.P에 존재하지 않고 B.N에만 존재하면(=A.P가 NULL이면) → Root(왜냐면 부모 노드가 없으니까)

3) 나머지는 Inner

 

후 이해하기 어렵다 ㅠㅠ

나중에 다시 풀어봐야지~~