[SQL][HackerRank] Binary Tree Nodes

 

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

Binary Tree Nodes | HackerRank

 

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.

문제에서는 N칼럼과 P칼럼으로 이루어진 BST라는 테이블이 주어진다. N은 각 노드의 값을 나타내고, P는 노드의 부모를 표현한다. 루트 노드의 부모는 없으므로, null로 표현되어있다.

 

이 BST 을 이용해 각 노드가 Root 노드인지, Leaf 노드인지, 아니면 Inner 노드인지 파악하는것이 문제의 목적이다. 원하는 출력형태는 아래와 같다.

 

이 문제는 CASE WHEN을 적절히 이용하면 해결 가능하고 특별히 Inner 노드를 판단할때 서브쿼리를 잘 작성해줘야한다. 루트 노드는 P에 null값이 있기때문에 쉽게 판단이 가능하다. 그리고 Inner 노드는 해당 노드가 누군가의 부모일 경우 해당된다. 이는 노드(N)가 부모(P)필드에 있는지 확인하는 방식으로 판단한다. 루트 노드도 누군가의 부모가 되는 경우이지만, CASE WHEN은 조건을 위에서부터 차례대로 고려하기 때문에 조건 작성에 문제가 되지 않는다.

 

아래와 같은 방식으로 서브쿼리를 작성해주면 서브쿼리로 값의 집합을 만들게 되는 것이며, 그 집합안에 N이 있는지 판단하게 된다.

CASE
  WHEN P IS NULL THEN 'Root'
  WHEN N IN (SELECT P FROM BST) THEN 'Inner'

 

그리고 마지막으로 위의 두경우에 모두 속하지 않으면 Leaf 노드로 분류해주면 된다. 그리고 노드의 순서대로 정렬해주면 문제를 해결할 수 있다.

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 1;