MySQL | HackerRank | Binary Tree Nodes

Problem

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:

---

요약

• N은 자식 노드, P는 N의 부모 노드
• 가장 상위의 노드라면 'Root'
  • N의 부모가 없는 경우 'Root'
  • P is null then 'Root'
• 가장 하위의 노드라면 'Leaf'
  • N의 부모가 있으며, N이 어느 누구의 부모 노드가 되지 않는 경우 'Leaf'
  • N not in P Value List
• 중간의 노드라면 'Inner'
  • N in P Value List

접근 방법

• row 별로 3가지의 case에 따라 아웃풋이 다르다 > Case When Then Else 문을 사용한다
• P Value List로 P값 파악이 필요하다 > Sub Query로 Value List를 만든다

---

정답

SELECT N,
    (CASE 
        WHEN P is null THEN 'Root'
        WHEN N in (SELECT distinct P 
        			FROM BST 
                    WHERE P is NOT NULL) THEN 'Inner'
        ELSE 'Leaf' 
    END) as Node 
FROM BST 
ORDER BY N

---

출처

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

Binary Tree Nodes | HackerRank